Given an unsorted Linked List, the task is to remove duplicates from the list.
Examples:
Input: linked_list = 12 -> 11 -> 12 -> 21 -> 41 -> 43 -> 21
Output: 12 -> 11 -> 21 -> 41 -> 43
Explanation: Second occurrence of 12 and 21 are removed.Input: linked_list = 12 -> 11 -> 12 -> 21 -> 41 -> 43 -> 21
Output: 12 -> 11 -> 21 -> 41 -> 43
Naive Approach to Remove Duplicates from an Unsorted Linked List:
The most simple approach to solve this, is to check each node for duplicate in the Linked List one by one.
Below is the Implementation of the above approach:
C++
/* C++ Program to remove duplicates in an unsorted linked list */#include <bits/stdc++.h>using namespace std;/* A linked list node */struct Node { int data; struct Node* next;};// Utility function to create a new Nodestruct 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; }}// Driver codeint 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("\nLinked list after removing duplicates "); printList(start); return 0;} |
C
/* C Program to remove duplicates in an unsorted linked list */#include <stdio.h>#include <stdlib.h>/* A linked list node */typedef struct Node { int data; struct Node* next;} Node;// Utility function to create a new NodeNode* newNode(int data){ Node* temp = (Node*)malloc(sizeof(Node)); temp->data = data; temp->next = NULL; return temp;}/* Function to remove duplicates from a unsorted linked list */void removeDuplicates(Node* start){ 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; free(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; }}/* 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("\nLinked list after removing duplicates "); printList(start); return 0;}// This code is contributed by Aditya Kumar (adityakumar129) |
Java
// Java program to remove duplicates from unsorted// linked listclass 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 */ 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("\n"); System.out.println( "Linked List after removing duplicates : "); list.printList(head); }}// This code has been contributed by Mayank Jaiswal |
Python3
# Python3 program to remove duplicates# from unsorted linked listclass Node(): def __init__(self, data): self.data = data self.next = Noneclass LinkedList(): def __init__(self): # Head of list self.head = None def remove_duplicates(self): ptr1 = None ptr2 = None dup = None ptr1 = self.head # Pick elements one by one while (ptr1 != None and ptr1.next != None): ptr2 = ptr1 # Compare the picked element with rest # of the elements while (ptr2.next != None): # 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 else: ptr2 = ptr2.next ptr1 = ptr1.next # Function to print nodes in a # given linked list def printList(self): temp = self.head while(temp != None): print(temp.data, end=" ") temp = temp.next print()# Driver codelist = LinkedList()list.head = Node(10)list.head.next = Node(12)list.head.next.next = Node(11)list.head.next.next.next = Node(11)list.head.next.next.next.next = Node(12)list.head.next.next.next.next.next = Node(11)list.head.next.next.next.next.next.next = Node(10)print("Linked List before removing duplicates :")list.printList()list.remove_duplicates()print()print("Linked List after removing duplicates :")list.printList()# This code is contributed by maheshwaripiyush9 |
C#
// C# program to remove duplicates from unsorted// linked listusing System;class List_ { Node head; class Node { public int data; public Node next; public Node(int d) { data = d; next = null; } } /* Function to remove duplicates from an unsorted linked list */ void remove_duplicates() { Node ptr1 = null, ptr2 = 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 */ ptr2.next = ptr2.next.next; } else /* This is tricky */ { ptr2 = ptr2.next; } } ptr1 = ptr1.next; } } void printList(Node node) { while (node != null) { Console.Write(node.data + " "); node = node.next; } } // Driver Code public static void Main(String[] args) { List_ list = new List_(); 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); Console.WriteLine( "Linked List_ before removing duplicates: "); list.printList(list.head); list.remove_duplicates(); Console.WriteLine(""); Console.WriteLine( "Linked List_ after removing duplicates: "); list.printList(list.head); }}// This code is contributed by gauravrajput1 |
Javascript
<script>// javascript program to remove duplicates from unsorted // linked list var head; class Node { constructor(val) { this.data = val; this.next = null; } } /* * Function to remove duplicates from an unsorted linked list */ function remove_duplicates() { var 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; } else /* This is tricky */ { ptr2 = ptr2.next; } } ptr1 = ptr1.next; } } function printList( node) { while (node != null) { console.log(node.data + " "); node = node.next; } } head = new Node(10); head.next = new Node(12); head.next.next = new Node(11); head.next.next.next = new Node(11); head.next.next.next.next = new Node(12); head.next.next.next.next.next = new Node(11); head.next.next.next.next.next.next = new Node(10); document.write("Linked List before removing duplicates : <br/> "); printList(head); remove_duplicates(); document.write("<br/>"); document.write("Linked List after removing duplicates : <br/> "); printList(head);// This code contributed by aashish1995</script> |
Output
Linked list before removing duplicates 10 12 11 11 12 11 10 Linked list after removing duplicates 10 12 11
Time Complexity: O(N2)
Auxiliary Space: O(1)
Remove duplicates from an Unsorted Linked List using Hashing:
The idea for this approach is based on the following observations:
- Traverse the link list from head to end.
- For every newly encountered element, check whether if it is in the hash table:
- if yes, remove it
- otherwise put it in the hash table.
- At the end, the Hash table will contain only the unique elements.
Below is the implementation of the above approach:
C++
/* C++ Program to remove duplicates in an unsorted linked list */#include <bits/stdc++.h>using namespace std;/* A linked list node */struct Node { int data; struct Node* next;};// Utility function to create a new Nodestruct 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 : \n"); printList(start); removeDuplicates(start); printf("\nLinked list after removing duplicates : \n"); printList(start); return 0;} |
Java
// Java program to remove duplicates// from unsorted linkedlistimport 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<Integer> 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( "\nLinked list after removing duplicates :"); printList(start); }}// This code is contributed by Rishabh Mahrsee |
Python3
# Python3 program to remove duplicates# from unsorted linkedlistclass Node: def __init__(self, data): self.data = data self.next = Noneclass LinkedList: def __init__(self): self.head = None # Function to print nodes in a # given linked list def printlist(self): temp = self.head while (temp): print(temp.data, end=" ") temp = temp.next # Function to remove duplicates from a # unsorted linked list def removeDuplicates(self, head): # Base case of empty list or # list with only one element if self.head is None or self.head.next is None: return head # Hash to store seen values hash = set() current = head hash.add(self.head.data) while current.next is not None: if current.next.data in hash: current.next = current.next.next else: hash.add(current.next.data) current = current.next return head# Driver codeif __name__ == "__main__": # Creating Empty list llist = LinkedList() llist.head = Node(10) second = Node(12) third = Node(11) fourth = Node(11) fifth = Node(12) sixth = Node(11) seventh = Node(10) # Connecting second and third llist.head.next = second second.next = third third.next = fourth fourth.next = fifth fifth.next = sixth sixth.next = seventh # Printing data print("Linked List before removing Duplicates.") llist.printlist() llist.removeDuplicates(llist.head) print("\nLinked List after removing duplicates.") llist.printlist()# This code is contributed by rajataro0 |
C#
// C# program to remove duplicates// from unsorted linkedlistusing System;using System.Collections.Generic;class removeDuplicates { class node { public int val; public 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<int> hs = new HashSet<int>(); // 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) { Console.Write(head.val + " "); head = head.next; } } // Driver code 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); Console.WriteLine("Linked list before removing " + "duplicates :"); printList(start); removeDuplicate(start); Console.WriteLine("\nLinked list after removing " + "duplicates :"); printList(start); }}// This code is contributed by amal kumar choubey |
Javascript
// JavaScript program to remove duplicates// from unsorted linkedlist class node { constructor(val) { this.val = val; this.next = null; } } /* Function to remove duplicates from a unsorted linked list */ function removeDuplicate( head) { // Hash to store seen values var hs = new Set(); /* Pick elements one by one */ var current = head; var prev = null; while (current != null) { var curval = current.val; // If current value is seen before if (hs.has(curval)) { prev.next = current.next; } else { hs.add(curval); prev = current; } current = current.next; } } /* Function to print nodes in a given linked list */ function printList( head) { while (head != null) { console.log(head.val + " "); head = head.next; } } /* * The constructed linked list is: 10->12->11->11->12->11->10 */ 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); console.log( "Linked list before removing duplicates :<br/>" ); printList(start); removeDuplicate(start); console.log( "<br/>Linked list after removing duplicates :<br/>" ); printList(start);// This code is contributed by todaysgaurav |
Output
Linked list before removing duplicates : 10 12 11 11 12 11 10 Linked list after removing duplicates : 10 12 11
Time Complexity: O(N), on average (assuming that hash table access time is O(1) on average).
Auxiliary Space: O(N), As extra space is used to store the elements in the stack.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
