链表概念

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检查或使程序更加清晰。这只是一个可能的解决方案。