Removing duplicate elements from unsorted Linked List

In previous post we have seen how to remove duplicate elements from sorted linked list. Here in this post we will see methods for removing duplicate elements from unsorted Linked List.

For example:

Input: 10->1->20->30->30->1->10->20
Output: 10->1->20->30

Method 1 : Use two loops

The simple method to solve this problem is to use two loops and compare each node with other nodes to see if it is duplicate or not. This method has a complexity of O(n2) where n is the number of nodes in the linked list.

Method 2: Using Hashing

In this method we will start with inserting head node in a hash table and traverse the linked list. for every node we will check if this node is present in hash table or not if this present in the hash table we will delete this node else we will insert this node in the hash table.

Below is the program for removing duplicate elements from an unsorted linked list.

#include<iostream>
#include<unordered_set>

using namespace std;

struct Node{
    int data;
    struct Node * next;
};


struct Node * newNode(int data){
    
    struct Node * temp = new Node;
    temp->data = data;
    temp->next = NULL;
    
    return temp;
}

void insert(struct Node **head, int data)
{
    if(*head == NULL)
      {*head = newNode(data);
        return;
      }
    struct Node *start = *head;
 
    while(start->next)
    {
        start = start->next;
    }
    
    start->next = newNode(data);
}

void printList(struct Node *head){
    
    while(head){
        cout<<head->data<<"->";
        head = head->next;
    }
    cout<<"NULL";
}

void removeDuplicate(struct Node *head){
    
    if(head== NULL)
      return;
      
     struct Node *prev = NULL; 
      
      unordered_set<int> set;
      
      while(head){
          if(set.find(head->data) == set.end())
             set.insert(head->data);
          else{
                prev->next = head->next;
                head = prev->next;
                continue;
            } 
          
          prev = head;
          head = head->next;
      }
    
}

int main(){
    struct Node *head = NULL;
    
    insert(&head,10);
    insert(&head,10);
    insert(&head,1);
    insert(&head,6);
    insert(&head,4);
    insert(&head,3);
    insert(&head,3);
    insert(&head,1);
    insert(&head,6);
    insert(&head,8);
    insert(&head,20);
    insert(&head,20);
    
    printList(head);
    cout<<endl;
    removeDuplicate(head);
    printList(head);
    
}

Output

10->10->1->6->4->3->3->1->6->8->20->20->NULL
10->1->6->4->3->8->20->NULL

 

If find any problem in the above programs please write it down in the comment box.

If you want to share any other method. Please write it to the contact@tutorialheap.com or you can also comment it down.

Leave a Reply

Your email address will not be published. Required fields are marked *