Remove Duplicates from Sorted List II

Medium Linked List Dummy Node Pattern Original on LeetCode

Remove Duplicates from Sorted List II is a medium linked list problem solved with the dummy node pattern pattern. The best approach, optimal (dummy node, skip runs), runs in O(n) time and O(1) space. Below are 2 approaches in Java, from brute force (count values) up.

Problem

Given a sorted linked list, delete every node whose value appears more than once, keeping only values that were distinct in the original list. Return the sorted result.

Examples

Example 1

Input: head = [1, 2, 3, 3, 4, 4, 5]
Output: [1, 2, 5]
Why: Every value that repeats is removed completely.

Example 2

Input: head = [1, 1, 1, 2, 3]
Output: [2, 3]

Constraints

The list has 0 to 300 nodes, sorted in non-decreasing order.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Brute force (count values)	`O(n)`	`O(n)`
Optimal (dummy node, skip runs)	`O(n)`	`O(1)`

1Brute force (count values)

TimeO(n)

SpaceO(n)

Count each value in a map, then rebuild the list with only values whose count is 1.

Count values.
Link together nodes whose value count is 1.

Java

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        Map<Integer, Integer> count = new HashMap<>();
        for (ListNode p = head; p != null; p = p.next) count.merge(p.val, 1, Integer::sum);
        ListNode dummy = new ListNode(), tail = dummy;
        for (ListNode p = head; p != null; p = p.next) {
            if (count.get(p.val) == 1) { tail.next = p; tail = p; }
        }
        tail.next = null;
        return dummy.next;
    }
}

2Optimal (dummy node, skip runs)

TimeO(n)

SpaceO(1)

prev stays on the last kept node. If the node after prev starts a run of equal values, skip the whole run by linking prev past it. Otherwise move prev forward.

prev = dummy; cur = head.
If cur.next has the same value, advance cur to the end of the run and set prev.next = cur.next.
Else prev = prev.next. Then cur = cur.next.

Java

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0, head), prev = dummy, cur = head;
        while (cur != null) {
            if (cur.next != null && cur.next.val == cur.val) {
                while (cur.next != null && cur.next.val == cur.val) cur = cur.next;
                prev.next = cur.next;
            } else {
                prev = prev.next;
            }
            cur = cur.next;
        }
        return dummy.next;
    }
}

Edge cases to test

Duplicates at the head
The whole list is duplicates
Duplicates at the tail

Hints

Hint 1

prev should point at the last node you know is unique. A dummy node covers duplicates at the head.

FAQ

What is the best time complexity for Remove Duplicates from Sorted List II?

Optimal (dummy node, skip runs) runs in O(n) time and O(1) extra space.

Which pattern does Remove Duplicates from Sorted List II use?

It is a linked list problem that uses the dummy node pattern pattern. Other problems with the same pattern: Remove Linked List Elements, Delete Nodes From Linked List Present in Array, Merge Two Sorted Lists.

Is there a brute force solution for Remove Duplicates from Sorted List II?

Yes. Brute force (count values) takes O(n) time and O(n) space. Count each value in a map, then rebuild the list with only values whose count is 1.

Which edge cases should I test for Remove Duplicates from Sorted List II?

Duplicates at the head; The whole list is duplicates; Duplicates at the tail.