# 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()
{
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);
// 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).