链接列表概念

Question

*node=*(node->next)中节点的值，如果节点是链表中的最后一个元素？

节点的值是否为NULL？

给出一个由N个节点组成的单链表。任务是从给定列表（如果存在）中删除重复项（具有重复值的节点）。注意：尽量不要使用多余的空间。预期时间复杂度为O（N）。节点以排序方式排列。

此解决方案不适用于测试用例2 2 2 2 2（五个值相等的节点）。

Node *removeDuplicates(Node *root)
{
    if(root->next==NULL)
        return root;

    Node * t1=root;
    Node* t2=root->next;
    while(t2!=NULL)
    {
        if(t1->data==t2->data)
        {
            *t2=*(t2->next);
        }
        else
        {
            t1=t1->next;
            t2=t2->next;
        }
    }
    return root;
}

此方法有效：

Node *removeDuplicates(Node *root)
{
    if(root->next==NULL)
        return root;

    Node * t1=root;
    Node* t2=root->next;
    while(t2!=NULL)
    {
        if(t1->data==t2->data)
        {
            if(t2->next==NULL)
            {
                t1->next=NULL;
                t2=NULL;
            }
            else
            {
                *t2=*(t2->next);
            }
        }
        else
        {
            t1=t1->next;
            t2=t2->next;
        }
    }
    return root;
}

Answer 1

通常，我不会为显然是家庭作业的东西发布完整的代码，但是我不确定如何正确表达所有要点。我也没有编译和运行它，因为我不想创建自己的Node类。

首先我们可以讨论算法。如果您的单链接列表已经排序并且NULL终止，那么从本质上讲，我们有一个当前节点指向该列表中的一个节点，还有一个沿着该列表向下移动的旅行节点（nextNode）。我们需要确保做的主要事情是一旦发现一个非重复项，则更新指向下一个节点的指针。

在下面的代码中，我还添加了NULL检查，这非常重要。养成确切知道变量可能处于哪种状态的习惯，因为很容易意外地在空指针上调用方法，这将导致程序崩溃。

Node* removeDuplicates(Node* root)
{
  // Check that root isn't null before checking that its next pointer is also not NULL
  if (root == NULL || root->next == NULL)
    return root;

  // Set up our current node and the travel node
  Node* currentNode = root;
  Node* nextNode = root->next;

  // Until we've reached the end of the singly linked list
  while (nextNode != NULL)
  {
    // Find the next node that isn't a duplicate
    // Also check that we don't reach the end of the list
    while (nextNode->data == currentNode->data && nextNode != NULL)
      nextNode = nextNode.next;

    // Update the current node's next pointer to point to the travel node
    currentNode->next = nextNode;

    // Update the current node to its next for the next iteration
    currentNode = nextNode;

    // Update the next node being careful to check for NULL
    nextNode = nextNode == NULL ? NULL : nextNode->next;
  }

  return root;
}

这不是解决此问题的唯一方法。通过在进行某些检查和关联时进行重组，可以消除一些NULL检查或使程序更清晰。这只是一种可能的解决方案。