Remove duplicates from a linked list

In this, we will see java code to remove duplicates from linked list

Java Code:

class LinkedList {
    static class Node {
        int data;
        Node next;

        Node(int d) {
            data = d;
            next = null;
        }
    }

    Node head;

    public void removeDuplicates() {
        if (head == null) {
            // List is empty
            return;
        }

        Node current = head;

        while (current != null) {
            Node runner = current;

            while (runner.next != null) {
                if (runner.next.data == current.data) {
                    // Remove the duplicate node
                    runner.next = runner.next.next;
                } else {
                    runner = runner.next;
                }
            }

            current = current.next;
        }
    }

 
}

The removeDuplicates method removes duplicates from the list. The method iterates over the list and, for each node, iterates over the remaining nodes to check for duplicates. If a duplicate is found, the method removes the duplicate node by skipping over it. The method does not remove the first occurrence of a value.

The time complexity of the above code to remove duplicates from a linked list is O(n^2) where n is the number of nodes in the linked list.

The reason for this time complexity is because for each node in the linked list, the code is iterating over the remaining nodes to check for duplicates. This nested loop structure results in a time complexity of O(n^2).

To achieve a time complexity of O(n), we can use a hash set to keep track of the unique elements in the linked list as we traverse it. Here’s the modified code that uses a hash set:

Java Code using HashSet to Achieve o(n) time complexity:

class LinkedList {
    static class Node {
        int data;
        Node next;

        Node(int d) {
            data = d;
            next = null;
        }
    }

    Node head;

    public void removeDuplicates() {
        if (head == null) {
            // List is empty
            return;
        }

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

        while (current != null) {
            if (set.contains(current.data)) {
                // Remove the duplicate node
                previous.next = current.next;
            } else {
                set.add(current.data);
                previous = current;
            }
            current = current.next;
        }
    }

  
}

In this modified code, we use a HashSet to keep track of the unique elements in the linked list as we traverse it. The Set interface provides constant-time complexity for the contains and add operations, so using a hash set results in a time complexity of O(n) for the removeDuplicates method.

The modified removeDuplicates method maintains a set of unique elements and uses it to remove duplicates from the linked list. The method iterates over each node in the linked list, and for each node, it checks if the node’s data is already in the set. If it is, the method removes the duplicate node by setting the next pointer of the previous node to the next node of the current node. If it’s not, the method adds the node’s data to the set and updates the previous pointer to the current node.

Thanks for Reading..