LeetCode 82: Remove Duplicates from Sorted List II Solution in Python Explained

Problem Statement

In LeetCode 82, you’re given the head of a sorted linked list, and you need to remove all nodes with duplicate values, leaving only distinct ones. Unlike LeetCode 83: Remove Duplicates from Sorted List, which keeps one instance of each value, here we eliminate all duplicates entirely. The output remains sorted.

Constraints

• Number of nodes: 0 <= n <= 300
• Node values: -100 <= Node.val <= 100
• The list is sorted in ascending order.

Example

Let’s check some cases:

Copy codeInput: head = [1,2,3,3,4,4,5]
Output: [1,2,5]
Explanation: 3 and 4 appear multiple times, so all are removed.

Copy codeInput: head = [1,1,1,2,3]
Output: [2,3]
Explanation: All 1s are duplicates and removed.

Copy codeInput: head = [1,2,3]
Output: [1,2,3]
Explanation: No duplicates, so no changes.

These examples clarify the goal: wipe out all duplicates completely.

Understanding the Problem

How do you tackle LeetCode 82: Remove Duplicates from Sorted List II in Python? Consider head = [1,2,3,3,4,4,5]. Since it’s sorted, duplicates are consecutive—3 appears twice, 4 appears twice—so we remove all 3s and 4s, leaving [1,2,5]. This isn’t a search task like LeetCode 1: Two Sum; it’s about list restructuring. We’ll use: 1. Iterative with Dummy Node: O(n) time, O(1) space—our best pick. 2. Recursive: O(n) time, O(n) space—a neat alternative.

Let’s start with the primary solution and explain it thoroughly.

Solution 1: Iterative with Dummy Node Approach (Primary)

Explanation

Modifying a linked list’s head can be tricky, so we use a dummy node to anchor our starting point. We’ll use two pointers: prev (tracks the last non-duplicate node) and curr (scans the list). If curr finds duplicates, we skip them all; if a value is unique, we connect it to prev.

For head = [1,2,3,3,4,4,5]:

• 1 is unique, keep it.
• 2 is unique, keep it.
• 3 repeats, skip all 3s.
• 4 repeats, skip all 4s.
• 5 is unique, keep it.

Result: [1,2,5].

Step-by-Step Example

Assume a ListNode class: class ListNode: def __init__(self, val=0, next=None): self.val = val; self.next = next.

Example 1: head = [1,2,3,3,4,4,5]

Goal: Return [1,2,5].

• Start: dummy = ListNode(0), dummy.next = head, prev = dummy, curr = head.
• Step 1: curr.val = 1, next is 2 (different), no duplicates.
• prev = 1, curr = 2.
• Step 2: curr.val = 2, next is 3, no duplicates.
• prev = 2, curr = 3.
• Step 3: curr.val = 3, next is 3, duplicates!
• Scan ahead: curr = 4 (past two 3s).
• prev.next = 4 (2 links to 4).
• Step 4: curr.val = 4, next is 4, duplicates!
• Scan ahead: curr = 5 (past two 4s).
• prev.next = 5 (2 links to 5).
• Step 5: curr.val = 5, next is None, no duplicates.
• prev = 5, curr = None.
• Finish: dummy.next = [1,2,5], return it.

Example 2: head = [1,1,1,2,3]

Goal: Return [2,3].

• Start: dummy.next = head, prev = dummy, curr = 1.
• Step 1: curr.val = 1, next is 1, duplicates!
• Scan ahead: curr = 2 (past three 1s).
• prev.next = 2 (dummy links to 2).
• Step 2: curr.val = 2, next is 3, no duplicates.
• prev = 2, curr = 3.
• Step 3: curr.val = 3, next is None, no duplicates.
• prev = 3, curr = None.
• Finish: dummy.next = [2,3], return it.

Example 3: head = [1,2,3]

Goal: Return [1,2,3].

• Start: prev = dummy, curr = 1.
• Step 1: curr.val = 1, next is 2, no duplicates.
• prev = 1, curr = 2.
• Step 2: curr.val = 2, next is 3, no duplicates.
• prev = 2, curr = 3.
• Step 3: curr.val = 3, next is None, no duplicates.
• prev = 3, curr = None.
• Finish: dummy.next = [1,2,3], return it.

How the Code Works (Iterative with Dummy Node) – Detailed Line-by-Line Explanation

Here’s the Python code with a meticulous breakdown:

Copy codeclass ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def deleteDuplicates(head: ListNode) -> ListNode:
    # Line 1: Check if the list is empty or has only one node
    if not head or not head.next:
        # If head is None (empty list) or head.next is None (one node), no duplicates can exist
        # Return the list as is (None or single node)
        return head

    # Line 2: Create a dummy node to act as a stable starting point
    dummy = ListNode(0)
    # Instantiates a new node with value 0 (value doesn’t matter) and next as None
    # This helps us handle cases where the head itself is part of duplicates

    # Line 3: Connect dummy to the head of the input list
    dummy.next = head
    # Sets dummy.next to the first node (e.g., 1 in [1,2,3,3,4,4,5])
    # Now the structure is: dummy -> 1 -> 2 -> ...

    # Line 4: Set prev pointer to dummy
    prev = dummy
    # prev starts at dummy, will eventually point to the last confirmed unique node
    # Initially, prev is our anchor before the actual list

    # Line 5: Set curr pointer to the head
    curr = head
    # curr starts at the first real node (e.g., 1), will scan through the list

    # Line 6: Loop while curr exists and has a next node to compare with
    while curr and curr.next:
        # Condition ensures we can check curr.val against curr.next.val
        # Stops if curr is None (end of list) or curr.next is None (last node)

        # Line 7: Check if the current node’s value equals the next node’s value
        if curr.val == curr.next.val:
            # If true, we’ve hit duplicates (e.g., 3 == 3 in [3,3,4])
            # We need to skip all nodes with this value

            # Line 8: Inner loop to move past all consecutive duplicates
            while curr.next and curr.val == curr.next.val:
                # Keeps advancing curr as long as the next node exists and matches the current value
                # e.g., for [3,3,4], moves curr from first 3 to second 3
                curr = curr.next
            # After this, curr is on the last duplicate (e.g., second 3)

            # Line 9: Move curr one step past the last duplicate
            curr = curr.next
            # Advances curr to the next unique value or None (e.g., from second 3 to 4)
            # This ensures we skip the entire duplicate sequence

            # Line 10: Update prev.next to skip the duplicates
            prev.next = curr
            # Links the last unique node (prev) to the next unique node (curr)
            # e.g., if prev is 2 and curr is 4, 2.next becomes 4, skipping [3,3]
        else:
            # If curr.val != curr.next.val, this node is unique (e.g., 1 then 2)

            # Line 11: Move prev to the current node
            prev = curr
            # Since curr is unique, prev advances to it (e.g., from 1 to 2)
            # prev now marks this node as part of the result

            # Line 12: Move curr to the next node
            curr = curr.next
            # Advances curr to check the next value (e.g., from 2 to 3)
            # Prepares for the next iteration

    # Line 13: Return the list starting from dummy.next
    return dummy.next
    # dummy.next points to the head of our cleaned list (e.g., [1,2,5])
    # Skips the dummy node, giving us the final result

This granular explanation ensures every action is clear, especially for beginners.

Alternative: Recursive Approach

Explanation

Recursion processes the list by breaking it into subproblems. For each node, check for duplicates: skip all if found, otherwise link to the recursive result.

For [1,2,3,3,4,4,5]:

• 1 is unique, recurse on [2,3,3,4,4,5].
• 2 is unique, recurse on [3,3,4,4,5].
• 3 repeats, skip to [4,4,5].
• 4 repeats, skip to [5].
• 5 is unique, return it.

Result: [1,2,5].

Step-by-Step Example (Alternative)

For head = [1,2,3,3,4,4,5]:

• Call 1: head = 1, head.next.val = 2, no duplicates.
• 1.next = recurse([2,3,3,4,4,5]).
• Call 2: head = 2, head.next.val = 3, no duplicates.
• 2.next = recurse([3,3,4,4,5]).
• Call 3: head = 3, head.next.val = 3, duplicates.
• Skip to recurse([4,4,5]).
• Call 4: head = 4, head.next.val = 4, duplicates.
• Skip to recurse([5]).
• Call 5: head = 5, head.next = None, return 5.
• Unwind: Return [1,2,5].

How the Code Works (Recursive)

Copy codedef deleteDuplicatesRecursive(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    if head.next and head.val == head.next.val:
        while head.next and head.val == head.next.val:
            head = head.next
        return deleteDuplicatesRecursive(head.next)
    else:
        head.next = deleteDuplicatesRecursive(head.next)
        return head

Complexity

• Iterative with Dummy Node:
• Time: O(n) – single pass.
• Space: O(1) – only pointers.
• Recursive:
• Time: O(n) – each node once.
• Space: O(n) – recursion stack.

Efficiency Notes

Iterative is best for its O(1) space and clarity, while recursive suits those exploring recursion, like in LeetCode 206: Reverse Linked List.

Key Insights

• Dummy Node: Simplifies head changes.
• Sorted Benefit: Duplicates are adjacent.
• Complete Removal: Skip all duplicates.

Additional Example

For head = [1,1,2,2,3]:

• Goal: [3].
• Iterative: Skip 1s, skip 2s, keep 3 → [3].

Edge Cases

• Empty List: [] → [].
• All Duplicates: [1,1,1] → [].
• No Duplicates: [1,2,3] → [1,2,3].

Both solutions handle these well.

Final Thoughts

LeetCode 82: Remove Duplicates from Sorted List II in Python is a great linked list test. The Iterative with Dummy Node solution is practical and efficient, while Recursive offers a slick alternative. Want more? Try LeetCode 83 for an easier take or LeetCode 80: Remove Duplicates from Sorted Array II for arrays. Ready to practice? Solve LeetCode 82 on LeetCode with [1,2,3,3,4,4,5] and aim for [1,2,5]—test your skills now!