AlgoMaster Logo

Remove Duplicates from Sorted List II

mediumFrequency5 min readUpdated June 23, 2026

Understanding the Problem

This problem is trickier than the basic "remove duplicates" variant (LeetCode #83). In that easier version, you keep one copy of each duplicate. Here, you remove all copies. If a value appears two or more times, every node with that value is gone.

Because the list is sorted, duplicates are always adjacent. We don't need a hash map to track counts. We only have to detect when consecutive nodes share the same value and then skip the entire run of that value.

The harder part is pointer management. When we delete nodes, we need to rewire the next pointer of the node before the duplicate group. If the duplicate group starts at the head, there is no node before it. A dummy node (also called a sentinel) solves this. It gives us a stable anchor before the head so every deletion follows the same rewiring step regardless of where it happens.

Key Constraints:

  • Number of nodes in range [0, 300] → The list can be empty, so the code must handle a null head without crashing.
  • Sorted in ascending order → Duplicates are guaranteed to be consecutive, so a single left-to-right scan can identify and remove every duplicate run without any extra data structure.

Approach 1: Hash Map (Two Pass)

Intuition

Count how many times each value appears, then keep only the values that appear exactly once. A hash map gives us those counts in one pass, and a second pass removes any node whose value has a count above one.

This ignores the sorted property entirely. It costs O(n) extra space for the map, but it would still work on an unsorted list, which makes it a useful baseline before we optimize.

Algorithm

  1. Traverse the entire list once, counting the frequency of each value in a hash map.
  2. Create a dummy node that points to the head.
  3. Traverse the list again with a pointer prev starting at the dummy node.
  4. For each node after prev, check its frequency in the map. If the count is greater than 1, skip it by setting prev.next = prev.next.next. Otherwise, advance prev to the next node.
  5. Return dummy.next as the new head.

Example Walkthrough

1Pass 1: count frequencies. Traverse entire list
1
current
2
3
3
4
4
5
null
1/6

Code

The hash map costs O(n) extra space. The sorted order makes that unnecessary: adjacent nodes already reveal duplicates, so the next approach removes them in a single pass with only a few pointers.

Approach 2: Single Pass with Dummy Node (Optimal)

Intuition

Because the list is sorted, every copy of a value sits in one contiguous block. We can detect the start of such a block by checking whether current.val == current.next.val. When that holds, we advance current past every node with that value, then rewire the previous unique node to skip the whole block at once.

The difference from the hash-map approach is that we never need an exact count. Comparing a node to its successor tells us whether the value is duplicated, which is all the decision requires. That removes the auxiliary map and brings space down to O(1).

A dummy node before the head keeps the rewiring uniform. Without it, a duplicate run that starts at the head would have no preceding node to rewire, forcing a separate case. The dummy supplies that preceding node, so prev.next = (node after the run) works at every position, including the front.

Algorithm

  1. Create a dummy node with dummy.next = head.
  2. Initialize prev = dummy. This pointer always points to the last confirmed unique node.
  3. Set current = head and traverse the list:
    • If current.next exists and current.val == current.next.val, we've found a duplicate run. Advance current until the value changes. Then set prev.next = current.next to skip the entire run.
    • Otherwise, the current node is unique. Advance prev to current.
  4. Advance current = current.next (or prev.next after a skip).
  5. Return dummy.next.

Example Walkthrough

1Initialize: dummy→1→2→3→3→4→4→5, prev=dummy, current=1
1
current
2
3
3
4
4
5
null
1/8

Code