Posted on by Kalkicode

# 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):
return

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

1. Start with the `current` pointer pointing to the head of the linked list.
2. For each `current` node, start an `innerCurrent` pointer from the same node.
3. Traverse through the linked list using the `innerCurrent` pointer: a. Check if the `innerCurrent` node's next node has the same value as the `current` node. If yes, skip the next node by updating the `innerCurrent` node's `next` pointer. b. If the values are different, move the `innerCurrent` pointer to the next node.
4. After the inner loop, move the `current` pointer to the next node.
5. Repeat steps 2-4 until the `current` pointer reaches the end of the linked list.

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

## Comment

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.

Categories
Relative Post