Remove Duplicates in Linked List

Today we will discuss how to remove duplicates in linked list but before we start the discussion make sure you know about linked list. Removing duplicates from a linked list is a very famous programming problem asked in many programming interviews. So, let's start, shall we?

Procedure

1. First we will make a linked list.

2. Now we will start traversing the list in such a way that the data in each node is compared with the data of every other node.

3. While traversing the list if we encounter a duplicate then we will assign that duplicate with some special value so that we can remember that it is a duplicate.

4. Then we will delete all the nodes with the special value.

Code

#include<iostream> using namespace std; struct node { int data; struct node* next; }; struct node* head=NULL; class linked { public: void insert(int x) { struct node* temp=new node(); temp->data=x; temp->next=NULL; if(head==NULL) { head=temp; } else { struct node* temp1=head; while(temp1->next!=NULL) { temp1=temp1->next; } temp1->next =temp; } } void duplicate() { struct node* temp=head; int count=0; while(temp!=NULL) { count++; temp=temp->next; } int p=0; temp=head; while(temp->next!=NULL && p<count) { struct node* temp1=temp->next; while(temp1!=NULL) { if(temp->data!=-1) { if(temp->data==temp1->data) { temp1->data=-1; } } temp1=temp1->next; } temp=temp->next; p++; } temp=head; struct node* temp1=head; while(temp->next!=NULL) { if(temp->next->data==-1) { temp1=temp; while(temp1->next!=NULL) { if(temp1->next->data!=-1) break; temp1=temp1->next; } temp->next=temp1->next; if(temp->next==NULL) break; } temp=temp->next; } } void disp() { struct node* temp=head; while(temp!=NULL) { cout<<temp->data<<" "; temp=temp->next; } cout<<endl; } }; int main() { linked l; l.insert(2); l.insert(5); l.insert(2); l.insert(6); l.insert(4); l.insert(5); l.insert(1); l.insert(3); l.insert(2); l.insert(6); l.insert(5); l.insert(2); l.insert(9); l.insert(7); l.insert(6); l.insert(2); l.insert(3); l.insert(3); l.insert(14); l.insert(2); l.disp(); l.duplicate(); l.disp(); return 0; }

Explanation of code(line by line)

1. First we will write a simple code of linked list which will have 2 functions:

     - insert() - which will insert elements in the linked list.
     - disp() - which will display the linked list.

2. Insert some values in the linked list.
3. Now we will make a function named duplicate() which will delete duplicates from a linked list.
4. We will make a pointer to node named temp which will point to head.
5. Then we will count the number of nodes.
6. Now we will start traversing the list such that every node is compared with every other node.
7. We will use temp to traverse from beginning till second last node and temp1(another pointer to node) to traverse from second node till last node. temp will traverse in outer loop and temp1 will traverse in inner loop.

8. In this way every temp node will be compared with every temp1 node .
9. To traverse temp from beginning till second last node we will use a variable named 'p' which will traverse the list till second last node.
10. Then we have declared temp1 and initialized it with the second node and after that we have started traversing temp1 till end.
11. Now if we encounter a duplicate then we will assign that node with value -1(special value). Then there is an if statement which will check if the data of a node is not -1 because there will be chances that a node with -1 value is encountered. So, this if statement will take care of that.

12. If the data of node is not -1 then we come in the inner if statement which checks if data of temp = data of temp1. If they are equal then we assign temp1 with -1 value.
13. Then we have incremented temp1, temp and p.

14. Then we have initialized temp with head. In the next line we have made a pointer to node temp1 initialized to head.

15. Then we have started iterating over the linked list using temp.

16. The first if condition checks if the data of next node is -1 or not.

17. If the data of next node is -1 then that means it it a duplicate and we have to delete it.

18. To delete we have used temp1 and iterated it over the linked list from the node where temp is currently present.

19. We iterate temp1 till the data of next node comes out to be -1, because there may be a situation in which multiple -1's are present consecutively. In that case we have to delete all those nodes.

while(temp1->next!=NULL)
{
       if(temp1->next->data!=-1)
              break;
       temp1=temp1->next;
}

20. Inside the loop for temp1 we have another if condition which checks if data of next node not -1 then we have to break out of the loop otherwise we will increment temp1.

21. After coming out of the loop of temp1 we have assigned temp->next = temp1->next which means temp's next will have the address of the next node which has data not equal to -1.

22. The next if statement is for the situation if the last node contains a duplicate then we break out of the loop.

if(temp->next==NULL)
break;

(try the code without including the above 2 statement and observe the output).

23. Then temp is incremented.