从排序链接列表中删除重复项

Question

我用 C++ 编写了以下代码，它从排序的链接列表中删除重复项。

#include <iostream>
using namespace std;

class Node
{
    public:
    int data;
    Node *next;
    
    Node(int data)
    {
        this->data = data;
        this->next = NULL;
    }
};


void push(Node* &head, Node* &tail, int data)
{
    if(head==NULL)
    {
        Node* newNode = new Node(data);
        head = newNode;
        tail = newNode;
        return;
    }
    
    else
    {
        Node* newNode = new Node(data);
        tail -> next = newNode;
        tail = newNode;
    }
}

void print(Node* &head)
{
    Node *temp = head;
    while(temp!=NULL)
    {
        cout<<temp->data<<" ";
        temp = temp->next;
    }
}

void removeDuplicates(Node* &head)
{
    if(head==NULL)
    {
        cout<<"Empty LL!";
        return;
    }
    
    if(head -> next == NULL) 
    {
        cout << "Single Node in LL" << endl;
        return ;
    }
    
    Node* curr = head;
    
    while(curr!=NULL)
    {
        if(curr->next!=NULL && (curr->data == curr->next->data))
        {
            Node* temp = curr->next;
            curr->next = curr->next->next;
            temp->next = NULL;
            delete temp;
            
        }
        
        else
        {
             curr = curr->next;
        }
    }
}


int main()
{
    Node* head = NULL;
    Node* tail = NULL;
    
    push(head, tail, 25);
    push(head, tail, 50);
    push(head, tail, 50);
    push(head, tail, 67);
    print(head);
    cout<<endl;
    removeDuplicates(head);
    print(head);
    return 0;
}

虽然代码运行良好，但我的疑问是，在“if”块中，删除重复节点后，为什么我们不更新 curr 的值，如 curr = curr -> next 再次将其发送到 while 循环。否则如何知道 curr 的更新值是多少？

PS：还是 C++ 的初学者:)

Answer 1

如果从列表中删除下一个节点，可能仍会留下更多重复项。如果你要前进curr，你只会删除所有其他重复元素。

当前代码会发生以下情况（^标记curr、---下一次迭代和任何非数字节点内容只是用来标记不同的节点）

1(a) -> 1(b) -> 1(c) -> 2(d)
^
---
1(a) -> 1(c) -> 2(d)
^
---
1(a) -> 2(d)
^
---
1(a) -> 2(d)
        ^

您建议的更改将导致以下结果

1(a) -> 1(b) -> 1(c) -> 2(d)
^
---
1(a) -> 1(c) -> 2(d)
        ^
---
1(a) -> 1(c) -> 2(d)
                ^