Given an unsorted linked list, delete duplicate nodes from it by traversing the list only once.
For example,
Output: 5 > 3 > 4 > 2 > 1 > null
Practice this problem
A simple solution would be to consider every distinct pair of nodes in the list and check if they have the same data or not. If their data matches, we delete the latter node. The time complexity of this solution is O[n2], where n is the total number of nodes in the linked list.
We can perform better by using hashing. The idea is to traverse the given list and insert each encountered node into a set. If the current node already presents in the set [i.e., it is seen before], ignore it and move to the next element. In the end, all duplicated nodes is removed from the list.
Following is the C++, Java, and Python program that demonstrates it:
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 | #include #include using namespace std; // A Linked List Node struct Node { int data; Node* next; }; // Helper function to print a given linked list void printList[Node* head] { Node* ptr = head; while [ptr] { cout data] != set.end[]] { previous->next = current->next; } else { // insert the current node into the set and proceed to the next node set.insert[current->data]; previous = current; } current = previous->next; } } int main[] { // input keys int keys[] = {5, 3, 4, 2, 5, 4, 1, 3}; int n = sizeof[keys]/sizeof[keys[0]]; // points to the head node of the linked list Node* head = nullptr; // construct a linked list for [int i = n-1; i >= 0; i--] { push[&head, keys[i]]; } removeDuplicates[head]; // print linked list printList[head]; return 0; } |
DownloadRun Code
Output:
5 > 3 > 4 > 2 > 1 > nullptr
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 | import java.util.HashSet; import java.util.Set; // A Linked List Node class Node { int data; Node next; Node[int data, Node next] { this.data = data; this.next = next; } } class Main { // Helper function to print a given linked list public static void printList[Node head] { Node ptr = head; while [ptr != null] { System.out.print[ptr.data + " > "]; ptr = ptr.next; } System.out.println["null"]; } // Function to remove duplicates from a sorted list public static Node removeDuplicates[Node head] { Node previous = null; Node current = head; // take an empty set to store linked list nodes for future reference Set set = new HashSet[]; // do till the linked list is empty while [current != null] { // if the current node is seen before, ignore it if [set.contains[current.data]] { previous.next = current.next; } else { // insert the current node into the set and proceed to the next node set.add[current.data]; previous = current; } current = previous.next; } return head; } public static void main[String[] args] { // input keys int[] keys = {5, 3, 4, 2, 5, 4, 1, 3}; // points to the head node of the linked list Node head = null; // construct a linked list for [int i = keys.length - 1; i >= 0; i--] { head = new Node[keys[i], head]; } removeDuplicates[head]; // print linked list printList[head]; } } |
DownloadRun Code
Output:
5 > 3 > 4 > 2 > 1 > null
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | # A Linked List Node class Node: def __init__[self, data=None, next=None]: self.data = data self.next = next # Helper function to print a given linked list def printList[head]: ptr = head while ptr: print[ptr.data, end=' > '] ptr = ptr.next print['None'] # Function to remove duplicates from a sorted list def removeDuplicates[head]: previous = None current = head # take an empty set to store linked list nodes for future reference s = set[] # do till the linked list is empty while current: # if the current node is seen before, ignore it if current.data in s: previous.next = current.next # insert the current node into the set and proceed to the next node else: s.add[current.data] previous = current current = previous.next return head if __name__ == '__main__': # input keys keys = [5, 3, 4, 2, 5, 4, 1, 3] # construct a linked list head = None for i in reversed[range[len[keys]]]: head = Node[keys[i], head] removeDuplicates[head] # print linked list printList[head] |
DownloadRun Code
Output:
5 > 3 > 4 > 2 > 1 > None
The time complexity of the above solution is O[n], where n is the total number of nodes in the linked list. The auxiliary space required by the program is O[n].
Similar post:
Remove duplicates from a sorted linked list