从未排序的链表中移动重复项时出错

Question

QSN。给定一个包含 N 个节点的未排序链表。任务是从这个未排序的链表中删除重复元素。当一个值出现在多个节点中时，应保留最先出现的节点，删除所有其他重复的节点。我尝试自己编写此代码，但显示此代码后附加的错误。

    class Solution
        {public: Node * removeDuplicates( Node *head) 
            { Node *curr =  head;
             Node *temp = head->next;
                while(curr!=NULL)
                {
                    temp = curr->next;
                    while(temp!=NULL)
                    {
                        if(curr->data == temp->data)
                        {
                            curr->next = temp->next;
                            temp = curr->next;
                        }
                        else
                        temp = temp->next;
                    }
                    curr = curr->next;
                }
            return head;
            }
        };

对于下面给出的一些测试用例，它不是 运行：

对于输入：1

6

2 2 2 3 4 2

你的输出： 2

预期输出： 2 3 4

Answer 1

我们可以使用unorederd_set来维护数据，使用prev指针来存储前一个节点的引用。如果数据不在集合中，我们将遍历链表，如果数据已存储，我们会将其添加到集合中，然后我们将使前一个节点指向当前注释的下一个节点，这样我们就可以删除重复项。

#include <bits/stdc++.h>
using namespace std;
class Solution{
    public: Node * removeDuplicates( Node *head) {
            Node *curr =  head;
            Node *temp = head->next;
            /*while(curr!=NULL){
                temp = curr->next;
                while(temp!=NULL){
                    if(curr->data == temp->data){
                        curr->next = temp->next;
                        temp = curr->next;
                    }else temp = temp->next;
                }
                curr = curr->next;
            }
            return head;
            */
            Node *prev;
            unordered_set<int> us;//To Store unique data
            while (curr != NULL){
                if( us.find(curr->data) == us.end()){//if not found in the set
                    prev=curr;
                    us.insert(curr->data);// adding to the set                      
                    curr=curr->next;//point to next one
                    
                }else{//found earlier in the set
                    prev->next=curr->next;
                    curr=curr->next;

                }
            }
            return head;
        }
};

完成程序在不使用集合的情况下删除重复节点记住这里我们使用前一个节点如果遇到的数据是duplicate 然后我们将使 previous node 指向 current nodenext node =31=] 这样我们就可以删除 当前节点（重复节点）。

代码：

#include <bits/stdc++.h>
using namespace std;

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

//Removes Duplicates using an ordered_set
Node * removeDuplicates( Node *head) {
    Node *curr =  head;
    Node *temp = head->next;
    /*while(curr!=NULL){
      temp = curr->next;
      while(temp!=NULL){
      if(curr->data == temp->data){
      curr->next = temp->next;
      temp = curr->next;
      }else temp = temp->next;
      }
      curr = curr->next;
      }
      return head;
      */
    Node *prev;
    unordered_set<int> us;//To Store unique data
    while (curr != NULL){
        if( us.find(curr->data) == us.end()){//if not found in the set
            prev=curr;
            us.insert(curr->data);// adding to the set                      
            curr=curr->next;//point to next one

        }else{//found earlier in the set
            prev->next=curr->next;
            curr=curr->next;

        }
    }
    return head;
}
//Removes duplicates with out using list 
//Here maintaining a prev node will do the trick
Node * deleteDuplicates(Node * head){
    Node * curr = head;
    //Iterating all over the linked nodes
    while ( curr != NULL ){
        Node * temp=curr->next;
        Node * prev = curr;
        while(temp != NULL){
            //if this data is already there in list
            if(temp->data == curr->data){
                prev->next=temp->next;
            }else{
                prev=temp;//notice our prev is temp when this data is not equal to curr->data
            }
            temp=temp->next;
        }
        curr=curr->next;
    }
    return head;
}
//add a node at the end
void addNodeAtEnd(Node * head,int data){
    Node * temp=head;
    while (temp->next != NULL)
        temp=temp->next;
    temp->next=new Node(data);
}
//displays all nodes
void printAllNodes(Node * head){
    Node * temp=head;
    while (temp != NULL){
        cout<<temp->data<<" ";
        temp=temp->next;
    }
    cout<<endl;
}
int main(){
    Node * head=new Node(5);
    addNodeAtEnd(head,20);
    addNodeAtEnd(head,30);
    addNodeAtEnd(head,30);
    addNodeAtEnd(head,30);
    addNodeAtEnd(head,5);
    addNodeAtEnd(head,30);
    addNodeAtEnd(head,40);
    addNodeAtEnd(head,50);
    addNodeAtEnd(head,30);
    addNodeAtEnd(head,50);
    addNodeAtEnd(head,20);
    printAllNodes(head);
    //head=removeDuplicates(head);
    head=deleteDuplicates(head);
    //displaying all the nodes after removing duplicates
    printAllNodes(head);
    return 0;
}

输出：

$ g++ Node.cpp && ./a.out
5 20 30 30 30 5 30 40 50 30 50 20 
5 20 30 40 50