Remove duplicates from an unsorted linked list
In previous post we are learning about how to Delete duplicate nodes in sorted linked list.
The challenge is to remove duplicate nodes from an unsorted singly linked list. Unlike the previous scenario where the list was sorted, this time we need to remove duplicate nodes from a list that isn't necessarily ordered. The objective is to have a linked list with only distinct elements while maintaining their original order.
Problem Description
Given an unsorted singly linked list, we want to modify it in such a way that all duplicate elements are removed, and only distinct elements are retained. The order in which the unique elements appear in the original list should be preserved.
Example
Consider the following unsorted linked list:
1 -> 2 -> 9 -> 4 -> 9 -> 3 -> 1 -> 7 -> 2 -> 1
After removing duplicates, the modified linked list should be:
1 -> 2 -> 9 -> 4 -> 3 -> 7
Idea to Solve the Problem


To solve this problem, we can use a nested loop approach. We iterate through each node in the linked list and for each node, we traverse the remaining nodes to find and remove duplicates of that node. This ensures that we remove all occurrences of a particular value except for the first one.
Pseudocode
removeDuplicates(linkedList):
if linkedList.head is NULL:
return
current = linkedList.head
while current is not NULL:
innerCurrent = current
while innerCurrent.next is not NULL:
if innerCurrent.next.data = current.data:
innerCurrent.next = innerCurrent.next.next
else:
innerCurrent = innerCurrent.next
current = current.next
Algorithm Explanation
- Start with the
current
pointer pointing to the head of the linked list. - For each
current
node, start aninnerCurrent
pointer from the same node. - Traverse through the linked list using the
innerCurrent
pointer: a. Check if theinnerCurrent
node's next node has the same value as thecurrent
node. If yes, skip the next node by updating theinnerCurrent
node'snext
pointer. b. If the values are different, move theinnerCurrent
pointer to the next node. - After the inner loop, move the
current
pointer to the next node. - Repeat steps 2-4 until the
current
pointer reaches the end of the linked list.
Code Solution
-
1) Remove duplicates from unsorted linked list in java
2) Remove duplicates from unsorted linked list in c#
3) Remove duplicates from unsorted linked list in c++
4) Remove duplicates from unsorted linked list in c
5) Remove duplicates from unsorted linked list in go
6) Remove duplicates from unsorted linked list in php
7) Remove duplicates from unsorted linked list in js
8) Remove duplicates from unsorted linked list in python
9) Remove duplicates from unsorted linked list in ruby
10) Remove duplicates from unsorted linked list in scala
11) Remove duplicates from unsorted linked list in swift
12) Remove duplicates from unsorted linked list in kotlin
Time Complexity
The time complexity of this algorithm is O(n^2), where n is the number of nodes in the linked list. This is because for each node, we potentially iterate through the remaining nodes to remove duplicates.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment