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

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 3 4 2

您的输出：2

预期输出：2 3 4

Answer 1

我们可以使用unorderd_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;
}
};

在不使用集合的情况下删除重复节点的完整程序记住这里我们使用的是上一个节点复，那么我们将使前一个节点指向当前节点的下一个节点(副本(。

代码：

#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