Remove duplicates from an unsorted singly linked list

We have an unsorted Linked List with n nodes, Out task is to remove duplicates from the list.

Example 1

Input: linked_list = 12 -> 11 -> 12 -> 21 -> 41 -> 43 -> 21

Output: 12 -> 11 -> 21 -> 41 -> 43

Explanation: The second occurrence of 12 and 21 are removed.

Example 2

Input: linked_list = 12 -> 11 -> 12 -> 21 -> 41 -> 43 -> 21

Output: 12 -> 11 -> 21 -> 41 -> 43

Approach

To remove the duplicates from an unsorted linked list. We need to keep track of visited nodes. We are using the HashSet to store the visited nodes. We will traverse the whole linked list and while traversing we’re checking if the node is already visited or not. If the node is visited then delete that node using two pointers and if not, we proceed to the next node.

The following are the steps to implement this logic

1. Create a HashSet to keep track of unique elements.
2. Initialize pointers (current and previous) to traverse the linked list.
3. Start iterating through the linked list using a while loop.
4. For each node in the linked list:

1. Check if the data of the current node is present in the HashSet.
2. If yes, it means it's a duplicate, so remove the current node by updating the next pointer of the previous node to skip the current node.
3. If no, add the data of the current node to the HashSet and move the pointers to the next node.

5. After the traversal, the linked list will have duplicates removed.

In summary, the algorithm uses a HashSet to keep track of unique elements encountered so far while traversing the linked list. If a duplicate is found, it is removed, and the traversal continues until the end of the linked list. This approach ensures that the resulting linked list contains only unique elements in their original order.

Complexity

• Time Complexity: O(N), where n is the number of nodes in the linked list.
• Space Complexity: O(K), where k is the number of unique elements in the linked list.

Code

# Java Code

import java.util.HashSet;

public class RemoveDuplicatesLinkedList {

    static class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    public static Node createLinkedList(int[] elements) {
        if (elements == null || elements.length == 0) {
            return null;
        }

        Node head = new Node(elements[0]);
        Node current = head;

        for (int i = 1; i < elements.length; i++) {
            current.next = new Node(elements[i]);
            current = current.next;
        }

        return head;
    }

    public static Node removeDuplicates(Node head) {
        if (head == null || head.next == null) {
            return head;
        }

        HashSet<Integer> seen = new HashSet<>();
        Node current = head;
        Node previous = null;

        while (current != null) {
            int data = current.data;

            if (seen.contains(data)) {
                // Remove the duplicate node
                previous.next = current.next;
            } else {
                // Add the data to the set
                seen.add(data);
                previous = current;
            }

            current = current.next;
        }

        return head;
    }

    public static void printList(Node head) {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] elements = { 12, 11, 12, 21, 41, 43, 21 };

        // Creating the linked list
        Node linkedList = createLinkedList(elements);

        System.out.println("Original linked list:");
        printList(linkedList);

        // Removing duplicates
        linkedList = removeDuplicates(linkedList);

        System.out.println("\nLinked list after removing duplicates:");
        printList(linkedList);
    }
}

Output

Original linked list:
12 11 12 21 41 43 21 

Linked list after removing duplicates:
12 11 21 41 43