## 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.

You can refer to this link for more information on 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.

**Recommended:** *Before stepping towards the solution try it by yourself on Coding Ninjas Studio.*

## 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;
}
}
static Node head;
// Function to insert node in the linked list
static void push(Node headM , int x)
{
Node temp = new Node(x);
temp.next = headM;
headM = temp;
head = headM;
}
Static void getResult(Node head)
{
Node temp1 = null, temp2 = null;
temp1 = head;
/* 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;
}
}
static void printList(Node head)
{
int c = 0;
while(head != null)
{
system.out.print(head.data + " ");
head = head.next;
c++;
}
}
public static void main(String[] args)
{
head = null;
push(head, 10);
push(head, 15);
push(head, 10);
push(head, 5);
push(head, 145);
push(head, 15);
push(head, 5);
push(head, 11);
push(head, 47);
push(head, 10);
push(head, 15);
push(head, 75);
System.out.println("Given Linked List :");
printList(head);
getResult(head);
System.out.println("");
System.out.println("Modified Linked List :");
printList(head);
}
}
```

```
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;
}
}
static Node head;
// Function to insert node in the linked list
static void push(Node headM , int x)
{
Node temp = new Node(x);
temp.next = headM;
headM = temp;
head = headM;
}
static void getResult(Node head, int k)
{
HashSet<Integer> duplicate = new HashSet<>();
node temp = head;
node previous = null;
// Traverse whole Linked List
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
{
duplicate.add(x);
previous = temp;
}
temp = temp.next;
}
}
// Function to print Linked List
static void printList(Node head)
{
int c = 0;
while(head != null)
{
system.out.print(head.data + " ");
head = head.next;
c++;
}
}
public static void main(String[] args)
{
head = null;
push(head, 10);
push(head, 15);
push(head, 45);
push(head, 17);
push(head, 145);
push(head, 125);
push(head, 5);
push(head, 11);
push(head, 47);
push(head, 43);
push(head, 1);
push(head, 75);
System.out.println("Given Linked List :");
printList(head);
getResult(head);
System.out.println("");
System.out.println("Modified Linked List :");
printList(head);
}
}
```

```
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.

## Frequently Asked Questions

### What are the types of the Linked list?

A linked list is of three types:- Singly Linked List, Doubly Linked List, and Circular Linked List.

### 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.

### What is the Circular Linked List?

In Circular Linked List, the tail of the linked list points to the head of the same linked list.

## Conclusion

In this article, we discussed the problem to **remove duplicates from an unsorted linked list** problem, discussed the various approaches to solving this problem programmatically, the time and space complexities, and how to optimize the approach by reducing the space complexity of the problem.

Refer to these amazing articles based on LinkedList data structureβ How to Master Linked List, Applications of LinkedList, LinkedList Vs. Arrays, and many more!!!

Suggested problems based on LinkedList are Remove Duplicates from Sorted List, Add One to LinkedList, Cycle Detection in Singly LinkedList, and many more.

I hope that this blog has helped you enhance your knowledge regarding the above Data Structures and Algorithms problem and if you would like to learn more, check out our articles on the Coding Ninjas Studio. Enroll in our courses, refer to the test series and problems available, and look at the interview experiences and interview bundle for placement preparations for big tech companies like Amazon, Microsoft, Google, and many more.

Do upvote our blogs if you find them helpful and engaging!