Remove duplicates from an unsorted linked list
Write a removeDuplicates() function that 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.
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 <iostream> #include <unordered_set> 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 << ptr->data << " —> "; ptr = ptr->next; } cout << "nullptr"; } // Helper function to insert a new node at the beginning of the linked list void push(Node** headRef, int data) { Node* newNode = new Node(); newNode->data = data; newNode->next = *headRef; *headRef = newNode; } // Function to remove duplicates from a sorted list void removeDuplicates(Node* head) { Node* previous = nullptr; Node* current = head; // take an empty set to store linked list nodes for future reference unordered_set<int> set; // do till the linked list is empty while (current != nullptr) { // if the current node is seen before, ignore it if (set.find(current->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