Remove all occurrences of duplicates from a sorted Linked List

Last Updated on February 25, 2022 by Ria Pathak

Remove all occurrences of duplicates from a sorted Linked List

In this problem, we are given a LinkedList (root node) and are asked to delete all the nodes occurring more than once. Let us see an example :-

Example

Input:

Output:

In the above linked list 4 and 10 were occurring more than once so we removed all their occurrences from our list.

To solve this question we simply traverse the list and compare every node with its next node.
If the next node is equal to the current node, we will delete the next node and move our pointer to the next of the next node. We will delete all the nodes equal to the current node and later delete the current node also because we have to delete all occurrences of a duplicate node.
If the current node is not equal to the next node we will not do anything because if there was any other node equal to the current node it will be just after it as the given list is sorted.

Approach

Algorithm

• Create a dummy node, dummy. dummy will act as a fake head and dummy.next will be head because we may have to remove the head itself.
• Create a previous node, prev. prev will always point to the end of the sublist containing unique values.
• Start traversing until the head is not null. As we have already used dummy as our fake head we can use head to traverse through the list as our current node.
• If head.data = head.next.data it means there is more than one occurrence of head in the list. Use an inner loop to skip all the nodes having the same data as head node.
• Otherwise, just move prev to its next node.
• Move head to its next node.

Code Implementation

Remove all occurrences of duplicates from a sorted Linked List

public class Prepbytes {
    static class Node {
        int data;
        Node next;

        Node() {
        };

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

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

        Node dummy = new Node(0);
        dummy.next = head;

        Node prev = dummy;

        while (head != null) {

            if (head.next != null && head.data == head.next.data) {

                while (head.next != null && head.data == head.next.data) {
                    head = head.next;
                }
                prev.next = head.next;

            } 
            else {
                prev = prev.next;
            }

            head = head.next;
        }
        return dummy.next;

    }

    public static void main(String[] args) {
        Node head = new Node(2);
        head.next = new Node(4);
        head.next.next = new Node(4);
        head.next.next.next = new Node(9);
        head.next.next.next.next = new Node(10);
        head.next.next.next.next.next = new Node(10);
        head.next.next.next.next.next.next = new Node(10);
        head.next.next.next.next.next.next.next = new Node(12);

        head = removeAllDuplicates(head);
        while (head != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }
    }
}

Time Complexity: O(n), we are traversing the list only once and traversing a list can be done in linear time.

[forminator_quiz id=”3425″]

So, in this blog, we have tried to explain the most efficient way to remove all occurrences of duplicates from a sorted linked list. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, visit PrepBytes Linked List.