RUN
C C++ JAVA PYTHON SQL HTML CSS DSA Robotics AWS SDE PREPARATION

Made with  & Code

# Remove duplicates from a linked list

Written By -

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;

}``````

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;

}``````

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