Topics › Linked List › Medium Problems of DLL

Remove duplicates from sorted DLL

Hard TUF ID 610 A2Z

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given the head of a doubly linked list whose values are sorted in non-decreasing order. Remove the duplicate nodes so that every value appears exactly once, keeping the first occurrence of each value, and return the head. The result must remain a valid doubly linked list: every prev pointer must match the corresponding next pointer, and the head’s prev must be null.

Constraints: 0 ≤ n ≤ 10^5, values fit in a 32-bit signed integer.

Example 1

head = 1 <-> 1 <-> 1 <-> 2 <-> 3 <-> 3 <-> 4
answer = 1 <-> 2 <-> 3 <-> 4

Example 2

head = 5 <-> 5 <-> 5 <-> 5
answer = 5                  // one value, one node

Example 3

head = 1 <-> 2 <-> 3
answer = 1 <-> 2 <-> 3      // already distinct

The sorted order is the key fact: all copies of a value sit next to each other, so “is this a duplicate” reduces to “does it equal its predecessor”.

Approach 1: Brute force, hash set of kept values

Intuition. Forget the sorting for a moment. Walk the list, remembering every value kept so far in a hash set. A node whose value is already in the set is a duplicate and is unlinked. This is the general solution for an unsorted list, and it is a fine first answer, but it spends O(n) memory on information that the sorted order already gives us for free.

Deletion in a doubly linked list needs no lookbehind pointer: cur.prev.next = cur.next and cur.next.prev = cur.prev bypass the node. The head is always kept (it is the first node seen, so its value is new), which means a duplicate always has a non-null prev.

Algorithm.

1. Create an empty set seen and set cur = head.
2. While cur is not null: save next = cur.next.
   • Try to add cur.val to seen. If it was already present, unlink cur: cur.prev.next = cur.next, and if cur.next exists, cur.next.prev = cur.prev. Clear cur’s pointers.
   • Move cur = next.
3. Return head.

static Node bruteForce(Node head) {
    Set<Integer> seen = new HashSet<>();
    Node cur = head;
    while (cur != null) {
        Node next = cur.next;
        if (!seen.add(cur.val)) {                     // add returns false when the value is already present
            cur.prev.next = cur.next;                 // a duplicate is never the head, so prev is non-null
            if (cur.next != null) cur.next.prev = cur.prev;
            cur.prev = null;
            cur.next = null;
        }
        cur = next;
    }
    return head;
}

Complexity. Time O(n): one pass with constant-time set operations on average. Space O(n) for the set, which in the worst case (all values distinct) stores every value.

Why is cur.prev safe to dereference? Every node that survives keeps correct links to its neighbours, and after each unlinking the following node’s prev is redirected to the last kept node. The head is kept, so by induction every node we examine after it has a non-null prev that is a kept node.

Approach 2: Optimal, skip each run of equal values

Intuition. In a sorted list every group of equal values is a contiguous run. Standing on the first node of a run (which we keep), walk a second pointer forward while it still sees the same value; the first node with a different value, or null, is where the next run starts. Connect the kept node directly to that position and continue from there. Each run costs one splice regardless of its length, and no memory is needed beyond two pointers.

Algorithm.

1. Set cur = head.
2. While cur and cur.next exist:
   • Set runEnd = cur.next and advance it while runEnd != null && runEnd.val == cur.val.
   • Set cur.next = runEnd; if runEnd is not null, set runEnd.prev = cur.
   • Move cur = runEnd.
3. Return head.

static Node optimal(Node head) {
    Node cur = head;
    while (cur != null && cur.next != null) {
        Node runEnd = cur.next;
        while (runEnd != null && runEnd.val == cur.val) runEnd = runEnd.next;   // first node with a different value, or null
        cur.next = runEnd;                            // splice out the whole run at once
        if (runEnd != null) runEnd.prev = cur;
        cur = runEnd;
    }
    return head;
}

Dry run on 1 <-> 1 <-> 1 <-> 2 <-> 3 <-> 3 <-> 4:

Result: 1 <-> 2 <-> 3 <-> 4.

Complexity. Time O(n): the inner runEnd pointer only ever moves forward over the whole list, so the two loops together touch each node a constant number of times. Space O(1).

The skipped nodes still point at each other and at nodes in the list, but nothing in the list points at them, so they are garbage. If you need them fully detached (for example to reuse them), clear their pointers in the inner loop; the asymptotic cost does not change.

Approach 3: Optimal, delete the next node one at a time

Intuition. The same idea can be written in a slightly different shape that some people find easier to reason about: stand on a node and, as long as the next node has the same value, delete that next node. Only after the next node differs do we step forward. Every deletion is a local three-pointer operation and the current node never changes while deleting, so there is no danger of losing our place.

Algorithm.

1. For cur from head, stepping to cur.next after each iteration:
2. While cur.next exists and cur.next.val == cur.val:
   • Let dup = cur.next. Set cur.next = dup.next; if dup.next exists set dup.next.prev = cur.
   • Clear dup’s pointers.
3. Return head.

static Node optimalOneAtATime(Node head) {
    for (Node cur = head; cur != null; cur = cur.next) {
        while (cur.next != null && cur.next.val == cur.val) {
            Node dup = cur.next;
            cur.next = dup.next;
            if (dup.next != null) dup.next.prev = cur;
            dup.prev = null;
            dup.next = null;
        }
    }
    return head;
}

Complexity. Time O(n): each node is either stepped onto once or deleted once. Space O(1).

Compared with Approach 2, this version performs one pointer update per duplicate instead of one per run, so it does marginally more work on long runs, but it fully detaches each removed node and never dereferences prev at all. The loop never touches the head’s prev, so the head remains the head with prev == null.

Edge cases and pitfalls

• Empty list. head == null must return null. All three loops exit immediately.
• Single node. Nothing to compare against; the node is returned as is.
• Everything equal. 5 <-> 5 <-> 5 <-> 5 collapses to a single node. In Approach 2, runEnd becomes null and cur.next is set to null; the guard before runEnd.prev = cur prevents a NullPointerException.
• Duplicates at the tail. 1 <-> 1 <-> 2 <-> 2 <-> 3 <-> 3 tests that the last run is handled when runEnd walks off the end.
• Fixing prev. Updating only next passes any forward-traversal test and breaks the first backward traversal. The test file checks that every next.prev points back at its node.
• Advancing through a deleted node. In Approach 1, cur.next is cleared during deletion; the code saves next beforehand. Approaches 2 and 3 never advance from a deleted node, so they need no saved pointer.
• Keeping the first occurrence. All three approaches keep the earliest node of each value; if the problem required keeping the last, the splice direction would flip.
• Unsorted input. Approaches 2 and 3 rely on equal values being adjacent and will leave non-adjacent duplicates in place. Approach 1 is the one that handles arbitrary order.

Related problems

• Delete all occurrences of a key in DLL uses the same unlinking step with a different criterion.
• Find Pairs with Given Sum in Doubly Linked List is another problem built on a sorted DLL.
• Remove duplicates from sorted array is the array version of the same run-skipping idea.
• Introduction to Doubly LL explains the node structure and the invariants a valid DLL must keep.