Remove duplicates from a linked list

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
#include <bits/stdc++.h>
using namespace std;

// LL node
struct Node
{
    int info;
    struct Node * next;
};

// function to create a new Node
struct Node* createNode(int info)
{
    Node *temp = new Node;
    temp->info = info;
    temp->next = NULL;
    return temp;
}

// Function removes duplicates from LL
void revdup(struct Node *first)
{
    struct Node *ptr1, *ptr2, *dupli;
    ptr1 = first;
    // Picking elements one at a time
    while (ptr1 != NULL && ptr1->next != NULL)
    {
        ptr2 = ptr1;
        // Comparing the picked element with rest elements
        while (ptr2->next != NULL)
        {
            // If duplicate then delete it
            if (ptr1->info == ptr2->next->info)
            {
                dupli = ptr2->next;
                ptr2->next = ptr2->next->next;
                delete(dupli);
            }
            else
                ptr2 = ptr2->next;
        }
        ptr1 = ptr1->next;
    }
}

// Function to print nodes of given LL
void printLL(struct Node *node)
{
    while (node != NULL)
    {
        printf("%d ", node->info);
        node = node->next;
    }
}

// Driver code
int main()
{
    /*The constructed linked list is:
    3, 4, 5, 1, 2, 4, 4*/
    struct Node *first = createNode(3);
    first->next = createNode(4);
    first->next->next = createNode(5);
    first->next->next->next = createNode(1);
    first->next->next->next->next = createNode(2);
    first->next->next->next->next->next = createNode(4);
    first->next->next->next->next->next->next = createNode(4);
    cout << "before removing the duplicate elements : ";
    printLL(first);
    revdup(first);
    cout << "after removing the duplicate elements : ";
    printLL(first);
    return 0;
}

Output

before removing the duplicate elements : 3 4 5 1 2 4 4
after removing the duplicate elements : 3 4 5 1 2 4 

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>
#include <unordered_set>
using namespace std;

// LL node
struct Node
{
    int info;
    Node * next;
};

// function to print given LL
void printLL(Node *first)
{
    Node *ptr = first;
    while (ptr)
    {
        cout << ptr->info;
        ptr = ptr->next;
        cout << ", ";
    }
    cout << "NULL";
}

// function to insert a new node in the beginning of LL
void push(Node **ref, int info)
{
    Node *createNode = new Node();
    createNode->info = info;
    createNode->next = *ref;
    *ref = createNode;
}

// Function to remove duplicates from unsorted list
void revdup(Node *first)
{
    Node *previous = nullptr;
    Node *present = first;
    // take an empty uno_set to store LL nodes
    unordered_set<int> uno_set;
    // until LL is empty
    while (present != nullptr)
    {
        // if present node is repeated, delete it
        if (uno_set.find(present->info) != uno_set.end())
        {
            previous->next = present->next;
            delete present;
        }
        else
        {
            // insert present node into the uno_set and go to next node
            uno_set.insert(present->info);
            previous = present;
        }
        present = previous->next;
    }
}

// driver code
int main()
{
    // input the LL(input)
    int input[] = { 3, 4, 5, 1, 2, 4, 4, 5, 6, 11, 18 };
    int size = sizeof(input) / sizeof(input[0]);
    // pointing first node of LL
    Node *first = nullptr;
    // build LL
    for (int i = size - 1; i >= 0; i--)
        push(&first, input[i]);
    revdup(first);
    printLL(first);
    return 0;
}

Output

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

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