{"post":"

Remove duplicates from a given linked list

Given: A link list(LL) that is not sorted and contains duplicate nodes. We have to remove these duplicate nodes.

Example:

Given LL: 13, 16, 13, 21, 25, 13, 30, 26, 13.

Output: 13, 16, 21, 25, 30, 26.

# Brute Force Approach

In this, we compare each element with the rest of the elements.

Code:

// Program to remove duplicates in an unsorted LL\n#include <bits/stdc++.h>\nusing namespace std;\n\n// LL node\nstruct Node\n{\n    int info;\n    struct Node * next;\n};\n\n// function to create a new Node\nstruct Node* createNode(int info)\n{\n    Node *temp = new Node;\n    temp->info = info;\n    temp->next = NULL;\n    return temp;\n}\n\n// Function removes duplicates from LL\nvoid revdup(struct Node *first)\n{\n    struct Node *ptr1, *ptr2, *dupli;\n    ptr1 = first;\n    // Picking elements one at a time\n    while (ptr1 != NULL && ptr1->next != NULL)\n    {\n        ptr2 = ptr1;\n        // Comparing the picked element with rest elements\n        while (ptr2->next != NULL)\n        {\n            // If duplicate then delete it\n            if (ptr1->info == ptr2->next->info)\n            {\n                dupli = ptr2->next;\n                ptr2->next = ptr2->next->next;\n                delete(dupli);\n            }\n            else\n                ptr2 = ptr2->next;\n        }\n        ptr1 = ptr1->next;\n    }\n}\n\n// Function to print nodes of given LL\nvoid printLL(struct Node *node)\n{\n    while (node != NULL)\n    {\n        printf(\"%d \", node->info);\n        node = node->next;\n    }\n}\n\n// Driver code\nint main()\n{\n    /*The constructed linked list is:\n    3, 4, 5, 1, 2, 4, 4*/\n    struct Node *first = createNode(3);\n    first->next = createNode(4);\n    first->next->next = createNode(5);\n    first->next->next->next = createNode(1);\n    first->next->next->next->next = createNode(2);\n    first->next->next->next->next->next = createNode(4);\n    first->next->next->next->next->next->next = createNode(4);\n    cout << \"before removing the duplicate elements : \";\n    printLL(first);\n    revdup(first);\n    cout << \"after removing the duplicate elements : \";\n    printLL(first);\n    return 0;\n}\n\n

Output

before removing the duplicate elements : 3 4 5 1 2 4 4\nafter removing the duplicate elements : 3 4 5 1 2 4 \n\n

Time Complexity: O(n2)

# Optimized Approach

We go through the LL from first to last. For each new element, we check if it is in the hash table. If it is there then we will remove it else we put it in the hash table.

Code:

#include <iostream>\n#include <unordered_set>\nusing namespace std;\n\n// LL node\nstruct Node\n{\n    int info;\n    Node * next;\n};\n\n// function to print given LL\nvoid printLL(Node *first)\n{\n    Node *ptr = first;\n    while (ptr)\n    {\n        cout << ptr->info;\n        ptr = ptr->next;\n        cout << \", \";\n    }\n    cout << \"NULL\";\n}\n\n// function to insert a new node in the beginning of LL\nvoid push(Node **ref, int info)\n{\n    Node *createNode = new Node();\n    createNode->info = info;\n    createNode->next = *ref;\n    *ref = createNode;\n}\n\n// Function to remove duplicates from unsorted list\nvoid revdup(Node *first)\n{\n    Node *previous = nullptr;\n    Node *present = first;\n    // take an empty uno_set to store LL nodes\n    unordered_set<int> uno_set;\n    // until LL is empty\n    while (present != nullptr)\n    {\n        // if present node is repeated, delete it\n        if (uno_set.find(present->info) != uno_set.end())\n        {\n            previous->next = present->next;\n            delete present;\n        }\n        else\n        {\n            // insert present node into the uno_set and go to next node\n            uno_set.insert(present->info);\n            previous = present;\n        }\n        present = previous->next;\n    }\n}\n\n// driver code\nint main()\n{\n    // input the LL(input)\n    int input[] = { 3, 4, 5, 1, 2, 4, 4, 5, 6, 11, 18 };\n    int size = sizeof(input) / sizeof(input[0]);\n    // pointing first node of LL\n    Node *first = nullptr;\n    // build LL\n    for (int i = size - 1; i >= 0; i--)\n        push(&first, input[i]);\n    revdup(first);\n    printLL(first);\n    return 0;\n}\n\n

Output

3, 4, 5, 1, 2, 6, 11, 18, NULL\n\n

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

\n","title":"Remove duplicates from a linked list","authorDetails":{"name":"Prabhnoor Maingi","slug":"prabhnoor-maingi"},"seo":{"title":"Remove duplicates from a linked list"},"description":"Here we will learn how to remove duplicates from a given linked list using brute force and an Optimized approach.","slug":"remove-duplicates-from-a-linked-list/","articleId":"636a83447bb1ce5072622b5e","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}