Remove Duplicates from a Sorted Doubly Linked List

Easy10–15 min

Topics

Linked ListDoubly Linked ListDeduplication

Companies

AmazonMicrosoft

Given the head of a doubly linked list already sorted in non-decreasing order, remove all duplicate values so each distinct value appears exactly once — keeping the list's relative order — and return the head. Since the list is sorted, duplicates are never scattered — they're always neighbors. That means each node only ever needs to check the one node right after it: no hash set or extra pass is needed to know whether a value has been seen before, unlike the unsorted "delete all occurrences of a key" problem.

Test Case 1:

Input:head = [1, 1, 2, 3, 3, 3, 7, 9, 9]

Output:[1, 2, 3, 7, 9]

Explanation:Consecutive runs of equal values collapse to one node each.

Test Case 2:

Input:head = [2, 2, 2]

Output:[2]

Explanation:The whole list is one run — it collapses to a single node.

Test Case 3:

Input:head = [1, 2, 3]

Output:[1, 2, 3]

Explanation:No value repeats, so nothing changes.

Constraints

◆0 ≤ number of nodes in head ≤ 200
◆-1000 ≤ node value ≤ 1000
◆head is already sorted in non-decreasing order, so every duplicate of a value sits consecutively

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Filter Consecutive Duplicates into a New Array

Good

Walk the list once, copying a value into an output array only when it differs from the array's last entry so far (skipping it whenever it repeats the previous value), then build a brand-new list from that array. Straightforward, but it allocates an array (and a whole new chain of nodes) the size of the deduplicated list.

TimeO(n)

SpaceO(n)

Java

Try it out

// Node definition used in this problem:
// class Node {
//     int val;
//     Node next;
// }

class Solution {
    public Node removeDupSortedDLL(Node head) {
        List<Integer> kept = new ArrayList<>();
        Node curr = head;
        while (curr != null) {
            if (kept.isEmpty() || kept.get(kept.size() - 1) != curr.val) {
                kept.add(curr.val);
            }
            curr = curr.next;
        }
        Node dummy = new Node(0);
        Node tail = dummy;
        for (int v : kept) {
            tail.next = new Node(v);
            tail = tail.next;
        }
        return dummy.next;
    }
}

Optimal — Bypass a Repeat as Soon as It's Seen

Optimal

Because the list is already sorted, every duplicate of a value is right next to it — there's no need to remember anything beyond the current node. Compare each node to the one after it: while the next node holds the same value, skip straight past it by redirecting curr.next; only advance curr once the next node's value actually differs. In a true doubly linked list, the node that survives would also get its .prev kept pointed correctly.