Remove Duplicates from Sorted List II: Delete All Duplicated Nodes

Remove Duplicates from Sorted List II is LeetCode 82. Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted.

This is not the same as removing extra copies of a value. If a value appears more than once, you remove every node with that value. The number is gone entirely.

Example 1: [1, 2, 3, 3, 4, 4, 5] becomes [1, 2, 5]

Example 2: [1, 1, 1, 2, 3] becomes [2, 3]

The challenge

The tricky part is that duplicates might start at the head. If the list is [1, 1, 2, 3], the head itself needs to be removed. That means you cannot just start iterating from head and keep a previous pointer, because there is no node before the head to link from.

You need a way to always have a "previous" node available, even when the head is being deleted. That is where the dummy head technique comes in.

The approach

The algorithm uses two key ideas:

1. Dummy head. Create a sentinel node that sits before the real head. Its next points to head. This guarantees that prev always has a valid node to work from, even if every real node gets deleted.

2. Skip-duplicates scan. Walk through the list with a curr pointer. At each position, check if curr and curr.next share the same value. If they do, keep advancing curr until you reach a node with a different value (or null). Then set prev.next = curr to skip over the entire duplicate group. If curr is unique, simply advance prev to curr.

The key insight: prev only advances when curr is confirmed unique. When duplicates are found, prev stays put while curr scans forward. Then prev.next is rewired to jump past all the duplicate nodes.

Visual walkthrough

Let's trace through [1, 2, 3, 3, 4, 4, 5] step by step. D is the dummy node.

Notice how prev stays at node 2 while both groups of duplicates (the 3s and the 4s) get skipped. The dummy node handles the case where duplicates appear at the head.

The solution

def deleteDuplicates(head):
    dummy = ListNode(0, head)
    prev = dummy

    curr = head
    while curr:
        if curr.next and curr.val == curr.next.val:
            while curr.next and curr.val == curr.next.val:
                curr = curr.next
            prev.next = curr.next
            curr = curr.next
        else:
            prev = curr
            curr = curr.next

    return dummy.next

The outer while walks every node. The inner while handles the skip: when a duplicate is found, it advances curr until it reaches the last node of the duplicate group. Then prev.next jumps to curr.next, cutting out every node in that group. The curr = curr.next after the skip moves curr to the first node after the group so the outer loop can continue.

Complexity analysis

Time: O(n). Each node is visited at most twice: once by the outer loop and possibly once by the inner skip loop. The two loops together cover each node a constant number of times.

Space: O(1). Only a dummy node and a few pointers. No extra data structures.

Edge cases

• All duplicates. Every value appears more than once, like [1, 1, 2, 2, 3, 3]. The dummy node saves you here. prev stays at the dummy the entire time, and dummy.next ends up as null. An empty list is returned.
• No duplicates. Every value is unique, like [1, 2, 3]. The inner loop never fires. prev advances with curr through the entire list. The original list is returned unchanged.
• Single node. Only one node, like [1]. The outer loop runs once, finds no duplicate (curr.next is null), and advances normally. The single node is returned.
• Duplicates at the head. [1, 1, 2, 3]. Without the dummy node, you would lose your entry point. The dummy handles this: prev stays at the dummy while the 1s are skipped, then dummy.next points to node 2.

The building blocks

This problem is built from two reusable techniques.

Dummy head technique. Adding a sentinel node before the real head eliminates the special case of modifying or deleting the first node. Instead of writing separate logic for "what if the head changes," you always have a prev pointer that is safe to update. After the algorithm finishes, dummy.next is the real head. This pattern appears in Merge Two Sorted Lists, Remove Nth Node From End, and anywhere the head might change.

Skip-duplicates scan. A while loop that advances through a group of consecutive equal values until it reaches a different value. This is the same scan you use in Remove Duplicates from Sorted Array and its variations. The sorted input guarantees that all duplicates are adjacent, so a single forward scan finds them all.

These two bricks combine naturally. The dummy head gives you a stable anchor. The skip scan identifies and removes duplicate groups. Together they solve the problem in one clean pass.

From understanding to recall

The logic of this problem is not hard to follow. You scan forward, skip duplicates, rewire pointers. Reading the solution, it makes sense. But under interview pressure, the details trip people up. Which pointer do you advance after a skip? When does prev move versus stay? Where exactly does prev.next point after the inner loop?

The fix is not re-reading. It is typing the solution from scratch, multiple times. The first attempt you will probably get the inner loop boundary wrong. By the third or fourth attempt, the two-loop structure and the prev/curr dance become automatic. That is when this problem stops being a source of bugs and starts being a free five minutes in an interview.

Related posts

• Remove Duplicates from Sorted List - The easier variant (LeetCode 83) where you keep one copy of each duplicate instead of removing all copies
• Reverse Linked List - The fundamental linked list pointer manipulation technique