# Remove duplicates from an unsorted linked list

Write a removeDuplicates() function which takes a list and deletes any duplicate nodes from the list. The list is not sorted.

For example if the linked list is 12->11->12->21->41->43->21 then removeDuplicates() should convert the list to 12->11->21->41->43.

METHOD 1 (Using two loops)
This is the simple way where two loops are used. Outer loop is used to pick the elements one by one and inner loop compares the picked element with rest of the elements.

Thanks to Gaurav Saxena for his help in writing this code.

## C++

 `/* Program to remove duplicates in an unsorted ` `   ``linked list */` `#include ` `using` `namespace` `std; ` ` `  `/* A linked list node */` `struct` `Node ` `{ ` `    ``int` `data; ` `    ``struct` `Node *next; ` `}; ` ` `  `// Utility function to create a new Node ` `struct` `Node *newNode(``int` `data) ` `{ ` `   ``Node *temp = ``new` `Node; ` `   ``temp->data = data; ` `   ``temp->next = NULL; ` `   ``return` `temp; ` `} ` ` `  `/* Function to remove duplicates from a ` `   ``unsorted linked list */` `void` `removeDuplicates(``struct` `Node *start) ` `{ ` `    ``struct` `Node *ptr1, *ptr2, *dup; ` `    ``ptr1 = start; ` ` `  `    ``/* Pick elements one by one */` `    ``while` `(ptr1 != NULL && ptr1->next != NULL) ` `    ``{ ` `        ``ptr2 = ptr1; ` ` `  `        ``/* Compare the picked element with rest ` `           ``of the elements */` `        ``while` `(ptr2->next != NULL) ` `        ``{ ` `            ``/* If duplicate then delete it */` `            ``if` `(ptr1->data == ptr2->next->data) ` `            ``{ ` `                ``/* sequence of steps is important here */` `                ``dup = ptr2->next; ` `                ``ptr2->next = ptr2->next->next; ` `                ``delete``(dup); ` `            ``} ` `            ``else` `/* This is tricky */` `                ``ptr2 = ptr2->next; ` `        ``} ` `        ``ptr1 = ptr1->next; ` `    ``} ` `} ` ` `  `/* Function to print nodes in a given linked list */` `void` `printList(``struct` `Node *node) ` `{ ` `    ``while` `(node != NULL) ` `    ``{ ` `        ``printf``(``"%d "``, node->data); ` `        ``node = node->next; ` `    ``} ` `} ` ` `  `/* Druver program to test above function */` `int` `main() ` `{ ` `    ``/* The constructed linked list is: ` `     ``10->12->11->11->12->11->10*/` `    ``struct` `Node *start = newNode(10); ` `    ``start->next = newNode(12); ` `    ``start->next->next = newNode(11); ` `    ``start->next->next->next = newNode(11); ` `    ``start->next->next->next->next = newNode(12); ` `    ``start->next->next->next->next->next = ` `                                    ``newNode(11); ` `    ``start->next->next->next->next->next->next = ` `                                    ``newNode(10); ` ` `  `    ``printf``(``"Linked list before removing duplicates "``); ` `    ``printList(start); ` ` `  `    ``removeDuplicates(start); ` ` `  `    ``printf``(````" Linked list after removing duplicates "````); ` `    ``printList(start); ` ` `  `    ``return` `0; ` `}`

## Java

 `// Java program to remove duplicates from unsorted  ` `// linked list ` ` `  `class` `LinkedList { ` ` `  `    ``static` `Node head; ` ` `  `    ``static` `class` `Node { ` ` `  `        ``int` `data; ` `        ``Node next; ` ` `  `        ``Node(``int` `d) { ` `            ``data = d; ` `            ``next = ``null``; ` `        ``} ` `    ``} ` ` `  `    ``/* Function to remove duplicates from an ` `       ``unsorted linked list */` `    ``void` `remove_duplicates() { ` `        ``Node ptr1 = ``null``, ptr2 = ``null``, dup = ``null``; ` `        ``ptr1 = head; ` ` `  `        ``/* Pick elements one by one */` `        ``while` `(ptr1 != ``null` `&& ptr1.next != ``null``) { ` `            ``ptr2 = ptr1; ` ` `  `            ``/* Compare the picked element with rest ` `                ``of the elements */` `            ``while` `(ptr2.next != ``null``) { ` ` `  `                ``/* If duplicate then delete it */` `                ``if` `(ptr1.data == ptr2.next.data) { ` ` `  `                    ``/* sequence of steps is important here */` `                    ``dup = ptr2.next; ` `                    ``ptr2.next = ptr2.next.next; ` `                    ``System.gc(); ` `                ``} ``else` `/* This is tricky */` `{ ` `                    ``ptr2 = ptr2.next; ` `                ``} ` `            ``} ` `            ``ptr1 = ptr1.next; ` `        ``} ` `    ``} ` ` `  `    ``void` `printList(Node node) { ` `        ``while` `(node != ``null``) { ` `            ``System.out.print(node.data + ``" "``); ` `            ``node = node.next; ` `        ``} ` `    ``} ` ` `  `    ``public` `static` `void` `main(String[] args) { ` `        ``LinkedList list = ``new` `LinkedList(); ` `        ``list.head = ``new` `Node(``10``); ` `        ``list.head.next = ``new` `Node(``12``); ` `        ``list.head.next.next = ``new` `Node(``11``); ` `        ``list.head.next.next.next = ``new` `Node(``11``); ` `        ``list.head.next.next.next.next = ``new` `Node(``12``); ` `        ``list.head.next.next.next.next.next = ``new` `Node(``11``); ` `        ``list.head.next.next.next.next.next.next = ``new` `Node(``10``); ` ` `  `        ``System.out.println(````"Linked List before removing duplicates : "````); ` `        ``list.printList(head); ` ` `  `        ``list.remove_duplicates(); ` `        ``System.out.println(``""``); ` `        ``System.out.println(````"Linked List after removing duplicates : "````); ` `        ``list.printList(head); ` `    ``} ` `} ` `// This code has been contributed by Mayank Jaiswal `

Output :

```Linked list before removing duplicates:
10 12 11 11 12 11 10
10 12 11 ```

Time Complexity: O(n^2)

METHOD 2 (Use Sorting)
In general, Merge Sort is the best-suited sorting algorithm for sorting linked lists efficiently.
1) Sort the elements using Merge Sort. We will soon be writing a post about sorting a linked list. O(nLogn)
2) Remove duplicates in linear time using the algorithm for removing duplicates in sorted Linked List. O(n)

Please note that this method doesn’t preserve the original order of elements.

Time Complexity: O(nLogn)

METHOD 3 (Use Hashing)
We traverse the link list from head to end. For every newly encountered element, we check whether it is in the hash table: if yes, we remove it; otherwise we put it in the hash table.

## C++

 `/* Program to remove duplicates in an unsorted ` `   ``linked list */` `#include ` `using` `namespace` `std; ` ` `  `/* A linked list node */` `struct` `Node ` `{ ` `    ``int` `data; ` `    ``struct` `Node *next; ` `}; ` ` `  `// Utility function to create a new Node ` `struct` `Node *newNode(``int` `data) ` `{ ` `   ``Node *temp = ``new` `Node; ` `   ``temp->data = data; ` `   ``temp->next = NULL; ` `   ``return` `temp; ` `} ` ` `  `/* Function to remove duplicates from a ` `   ``unsorted linked list */` `void` `removeDuplicates(``struct` `Node *start) ` `{ ` `    ``// Hash to store seen values ` `    ``unordered_set<``int``> seen; ` ` `  `    ``/* Pick elements one by one */` `    ``struct` `Node *curr = start; ` `    ``struct` `Node *prev = NULL; ` `    ``while` `(curr != NULL) ` `    ``{ ` `        ``// If current value is seen before ` `        ``if` `(seen.find(curr->data) != seen.end()) ` `        ``{ ` `           ``prev->next = curr->next; ` `           ``delete` `(curr); ` `        ``} ` `        ``else` `        ``{ ` `           ``seen.insert(curr->data); ` `           ``prev = curr; ` `        ``} ` `        ``curr = prev->next; ` `    ``} ` `} ` ` `  `/* Function to print nodes in a given linked list */` `void` `printList(``struct` `Node *node) ` `{ ` `    ``while` `(node != NULL) ` `    ``{ ` `        ``printf``(``"%d "``, node->data); ` `        ``node = node->next; ` `    ``} ` `} ` ` `  `/* Driver program to test above function */` `int` `main() ` `{ ` `    ``/* The constructed linked list is: ` `     ``10->12->11->11->12->11->10*/` `    ``struct` `Node *start = newNode(10); ` `    ``start->next = newNode(12); ` `    ``start->next->next = newNode(11); ` `    ``start->next->next->next = newNode(11); ` `    ``start->next->next->next->next = newNode(12); ` `    ``start->next->next->next->next->next = ` `                                    ``newNode(11); ` `    ``start->next->next->next->next->next->next = ` `                                    ``newNode(10); ` ` `  `    ``printf``(````"Linked list before removing duplicates : "````); ` `    ``printList(start); ` ` `  `    ``removeDuplicates(start); ` ` `  `    ``printf``(````" Linked list after removing duplicates : "````); ` `    ``printList(start); ` ` `  `    ``return` `0; ` `} `

## Java

 `// Java program to remove duplicates ` `// from unsorted linkedlist ` ` `  `import` `java.util.HashSet; ` ` `  `public` `class` `removeDuplicates  ` `{ ` `    ``static` `class` `node  ` `    ``{ ` `        ``int` `val; ` `        ``node next; ` ` `  `        ``public` `node(``int` `val)  ` `        ``{ ` `            ``this``.val = val; ` `        ``} ` `    ``} ` `     `  `    ``/* Function to remove duplicates from a ` `       ``unsorted linked list */` `    ``static` `void` `removeDuplicate(node head)  ` `    ``{ ` `        ``// Hash to store seen values ` `        ``HashSet hs = ``new` `HashSet<>(); ` `     `  `        ``/* Pick elements one by one */` `        ``node current = head; ` `        ``node prev = ``null``; ` `        ``while` `(current != ``null``)  ` `        ``{ ` `            ``int` `curval = current.val; ` `             `  `             ``// If current value is seen before ` `            ``if` `(hs.contains(curval)) { ` `                ``prev.next = current.next; ` `            ``} ``else` `{ ` `                ``hs.add(curval); ` `                ``prev = current; ` `            ``} ` `            ``current = current.next; ` `        ``} ` ` `  `    ``} ` `     `  `    ``/* Function to print nodes in a given linked list */` `    ``static` `void` `printList(node head)  ` `    ``{ ` `        ``while` `(head != ``null``)  ` `        ``{ ` `            ``System.out.print(head.val + ``" "``); ` `            ``head = head.next; ` `        ``} ` `    ``} ` ` `  `    ``public` `static` `void` `main(String[] args)  ` `    ``{ ` `        ``/* The constructed linked list is: ` `         ``10->12->11->11->12->11->10*/` `        ``node start = ``new` `node(``10``); ` `        ``start.next = ``new` `node(``12``); ` `        ``start.next.next = ``new` `node(``11``); ` `        ``start.next.next.next = ``new` `node(``11``); ` `        ``start.next.next.next.next = ``new` `node(``12``); ` `        ``start.next.next.next.next.next = ``new` `node(``11``); ` `        ``start.next.next.next.next.next.next = ``new` `node(``10``); ` ` `  `        ``System.out.println(``"Linked list before removing duplicates :"``); ` `        ``printList(start); ` ` `  `        ``removeDuplicate(start); ` ` `  `        ``System.out.println(````" Linked list after removing duplicates :"````); ` `        ``printList(start); ` `    ``} ` `} ` ` `  `// This code is contributed by Rishabh Mahrsee `

Output :

```Linked list before removing duplicates:
10 12 11 11 12 11 10
10 12 11 ```

Thanks to bearwang for suggesting this method.

Time Complexity: O(n) on average (assuming that hash table access time is O(1) on average).

Please write comments if you find any of the above explanations/algorithms incorrect, or a better ways to solve the same problem.