链表概念

Question

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

节点的值是否为 NULL？

Given a singly linked list consisting of N nodes. The task is to remove duplicates (nodes with duplicate values) from the given list (if exists). Note: Try not to use extra space. Expected time complexity is O(N). The nodes are arranged in a sorted way.

此解决方案不适用于测试用例 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

通常我不会 post 显然是家庭作业的完整代码，但我不确定如何正确表达所有要点。我也没有编译运行这是因为我不想创建自己的节点 class.

首先我们可以谈谈算法。如果您的单向链表已经排序并且 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 检查或使程序更清晰。这只是一种可能的解决方案。

链表概念

Linked list concepts

c++

linked-list

data-structures

singly-linked-list

c++11