Last Updated: Jun 30, 2023
Medium

# Remove Duplicates From an Unsorted Linked List

Harsh Goyal
1 upvote

## Introduction

This blog will discuss the various approaches to solve the Remove duplicates from an unsorted linked list problem. Before jumping into the problem of removing duplicates from an unsorted linked list, letβs first understand a Linked list.

A Linked list is a kind of data structure in which the elements are connected using pointers, and each node has the address of the pointer of its next node.

In this Remove duplicates from an unsorted linked list problem, we need to return the head of the linked list after removing all the duplicates from the linked list.

For Example:-

List :- 10 -> 15 -> 10 -> 5 -> 145 -> 15 -> 5 -> 11 -> 47 -> 10 -> 15 -> 75

Output :- 10 -> 15 -> 5 -> 145 -> 11 -> 47 -> 75

Let's move toward the approach section for this problem and know how to solve this in the Java language.

## Brute Force Approach

Brute Force Solution considers checking the complete linked list for the duplicate of each and every element using the nested loop and removing that duplicate element.

### Algorithm

Step 1. Create a function βgetResult()β that will accept one parameter, i.e., one head pointer of the linked list.

Step 2. Initialize two variables: βtemp1β will keep track of the element whose duplicates are being checked, and βtemp2β will keep track of the node that is being checked for the duplicate.

Step 3. Assign the value of βheadβ to βtemp1β and assign the null value to βtemp2β.

Step 4. Make an iteration using the βwhileβ loop, which will terminate if the value of βtemp1β or the βnextβ pointer of βtemp1β is equal to null.

Step 5. Store value of βtemp1β in βtemp2β.

Step 6. Make one nested iteration using the βwhileβ loop, which will terminate if the value of the βnextβ pointer of βtemp2β is equal to null.

Step 7. Check if the value of both the βtemp1β and βtemp2β are equal or not, if they are equal, delete that node and increment the next pointer of βtemp2β to its next nodeβs next pointer and if not equal, then only increment it once.

Step 8. Increment the βnextβ pointer of the βtemp1β node to its next node.

### Java Solution

``````public class Solution
{
class Node
{
// Basic structure of the Node
int data;
Node next;
// Constructor of this class βNodeβ
Node(int x)
{
data = x;
Next = null;
}
}

// Function to insert node in the linked list
static void push(Node headM , int x)
{
Node temp = new Node(x);
}

{
Node temp1 = null, temp2 = null;

/* Pick elements one by one */
while (temp1 != null && temp1.next != null)
{
temp2 = temp1;

/* Comparing each element with the complete linked list
while (temp2.next != null)
{
/* If duplicate of that node is present, then delete it */
if (temp1.data == temp2.next.data)
{
temp2.next = temp2.next.next;
System.gc();
}
else
{
temp2 = temp2.next;
}
}
temp1 = temp1.next;
}
}

{
int c = 0;
{
c++;
}
}

public static void main(String[] args)
{
System.out.println("");
}
}``````

``````Output :

Given Linked List:- 10 -> 15 -> 10 -> 5 -> 145 -> 15 -> 5 -> 11 -> 47 -> 10 -> 15 -> 75

Modified Linked List:-  10 -> 15 -> 5 -> 145 -> 11 -> 47 -> 75 ``````

### Complexity Analysis

Time Complexity: O(N ^ 2)

Incall to βgetResult()β, As we are using the nested loop to check for a duplicate of each element and then removing it, therefore, the overall time complexity is O(N ^ 2).

Space Complexity: O(1)

As we are using constant space, therefore, the overall space complexity will be O(1).

Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm

## Optimized Approach

To optimize this, Remove duplicates from an unsorted linked list problem; weβll try to optimize the time complexity using the concept of hashing; in this approach, we will keep track of the node, if the node is already present in the hashmap, then it means it is the duplicate of that node, and we need to remove this duplicate node, and if that node is not present in that map, then this means that this is newly encountered node and we need to add this in the map.

### Algorithm

Step 1. Create a function βgetResult()β that will accept one parameter, i.e., one βheadβ pointer of the linked list..

Step 2. Create an unordered Hashset βduplicateβ using βCollectionβ.

Step 3. Initialize two variables: βtempβ will keep track of the element whose duplicates are being checked, and βpreviousβ will keep track of the previous node of the βtempβ.

Step 4. Assign the value of βheadβ to βtempβ and assign the null value to βpreviousβ.

Step 5. Make an iteration using the βwhileβ loop, which will terminate if the value of βtempβ is βnullβ.

Step 6. Assign the value of data of βtempβ to a variable βxβ.

Step 7. Check if the value of βxβ is already in the βduplicateβ Hashset or not.

Step 8. If it is present in the map then we need to assign the value of the βnextβ pointer of βtempβ to the βnextβ pointer of βpreviousβ, and if it is not present in the map, then add that value of βxβ in the map and make βpreviousβ equal to βtempβ.

Step 9. Assign the value of the βnextβ pointer of βtempβ to βtempβ.

### Java Solution

``````public class Solution
{
class Node
{
// Basic structure of the Node
int data;
Node next;
// Constructor of this class βNodeβ
Node(int x)
{
data = x;
Next = null;
}
}

// Function to insert node in the linked list
static void push(Node headM , int x)
{
Node temp = new Node(x);
}

static void getResult(Node head, int k)
{
HashSet<Integer> duplicate = new HashSet<>();

node previous = null;

while (temp != null)
{
int x = temp.val;

// If the value of that node is already present in the map
if (duplicate.contains(x))
{
previous.next = temp.next;
}
else
{
previous = temp;
}
temp = temp.next;
}
}

// Function to print Linked List
{
int c = 0;
{
c++;
}
}

public static void main(String[] args)
{

System.out.println("");

}

}``````

``````Output :

Given Linked List:- 10 -> 15 -> 10 -> 5 -> 145 -> 15 -> 5 -> 11 -> 47 -> 10 -> 15 -> 75

Modified Linked List:-  10 -> 15 -> 5 -> 145 -> 11 -> 47 -> 75 ``````

### Complexity Analysis

Time Complexity: O(N)

Incall to βgetResult()β, We are just traversing the whole linked list of length βNβ and checking for each node in the map, therefore, the average time complexity will be O(N), taking into consideration that accesses hash table is O(1).

Space Complexity: O(N)

As we are using a hash table that will be of size βNβ in the worst case, therefore, the overall space complexity is O(N).

Check out this problem - Find Duplicate In Array

To understand it better and know proper code implementation, you should watch this video.

### What is the difference between Singly Linked List and Doubly Linked List?

In Singly Linked List, each node has the address of the pointer to its next node, whereas, in Doubly Linked List, each node has the address of the pointers of its next node and its previous node.