从排序的链表中删除重复项-解网

问：

我用 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++ :)的初学者

c++ 数据结构 while-loop 链接列表

我非常头痛，所以我的分析可能是错误的。循环看起来正确。它表示如果下一个节点存在并且包含与当前节点相同的值，请将其删除并将链接切换到指向下一个>下一个节点，这是正确的。您不需要推进电流，因为您想测试当前和下一个 -> 之间的值。

2赞 Richard Critten 6/11/2023

如果它们相等，则该函数会删除我们现在所在位置前面的节点：即，如果我们有一个节点列表：A -> B -> C -> D，它会检查 A 是否 == B，如果它们相同，则删除 B。现在下次循环时，它仍然在 A 上，因为它需要在继续之前检查 A == C。removeDuplicates

答：

3赞 Ted Lyngmo 6/11/2023 #1

我们为什么不更新 like 的值currcurr = curr -> next

因为您希望不受删除的影响，以便您也可以将其与删除后的下一个节点进行比较。列表中可能有多个重复项，您希望删除除第一个副本之外的所有重复项。curr

5赞 fabian 6/11/2023 #2

如果从列表中删除下一个节点，可能还会有更多重复项。如果你前进，你只会擦除所有其他重复的元素。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)
                ^

上一个：如何在不填充所有 cin 变量的情况下打破循环？

下一个：在 C++ while 循环中获得无限循环，为什么会发生这种情况？[已结束]

从排序的链表中删除重复项

Removing Duplicates from a Sorted Linked List

评论