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, Python, C++ and JavaScript, 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.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

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.

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 code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
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.

  1. Count values.
  2. Link together nodes whose value count is 1.
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.

  1. prev = dummy; cur = head.
  2. If cur.next has the same value, advance cur to the end of the run and set prev.next = cur.next.
  3. Else prev = prev.next. Then cur = cur.next.
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.