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

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.

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.