error in rmoving duplicates from unsorted linked list

user_16727699 0
Viewed 73

QSN. Given an unsorted linked list of N nodes. The task is to remove duplicate elements from this unsorted Linked List. When a value appears in multiple nodes, the node which appeared first should be kept, all others duplicates are to be removed. I tried to write this code on my own but showing error i attached after this code.

    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;
            }
        };

It is not running for some testcases given below:

For Input: 1

6

2 2 2 3 4 2

Your Output: 2

Expected Output: 2 3 4

pointers linked-list c++
1 Answers

we can use unorederd_set to maintain the data and use prev pointer to store the reference of previous node. We will iterate over the linked list if the data is not in the set we will add it to set if it is stored then we will make the previous node to point to the next of current note this way we can remove duplicates.

#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;
        }
};

Complete program where to remove duplicate nodes without using set remember here we are using a previous node if data encountered is duplicate then we will make the previous node to point to the next node of current node this way we can remove the current node(the duplicate one).

Code:

#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;
}

Output :

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