LeetCode 203: Remove Linked List Elements Solution in Python Explained

Problem Statement

In LeetCode 203: Remove Linked List Elements, you’re given:

• head: The head node of a singly linked list.
• val: An integer value to remove from the list.
• Your task is to return the head of the modified list with all nodes containing val removed.

Each node has a val (value) and a next pointer to the next node or None. This differs from number-based problems like LeetCode 202: Happy Number, focusing instead on pointer manipulation in a linked structure.

Constraints

• Number of nodes: 0 ≤ n ≤ 10⁴.
• Node values: 1 ≤ val ≤ 50.
• Input val: 1 ≤ val ≤ 50.

Examples

Let’s see some cases (list notation for clarity):

Copy codeInput: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]
Explanation: Remove all nodes with value 6.

Copy codeInput: head = [], val = 1
Output: []
Explanation: Empty list remains empty.

Copy codeInput: head = [7,7,7,7], val = 7
Output: []
Explanation: Remove all nodes (all are 7).

These examples show we’re pruning nodes based on a target value.

Understanding the Problem

How do we solve LeetCode 203: Remove Linked List Elements in Python? Imagine a list 1 → 2 → 6 → 3 → 4 → 5 → 6 and val = 6. We need to skip the two 6 nodes, resulting in 1 → 2 → 3 → 4 → 5. A naive approach might struggle with head nodes or consecutive matches, but linked list manipulation thrives on pointer adjustments. This isn’t a bit operation like LeetCode 201: Bitwise AND of Numbers Range; it’s about restructuring links. We’ll use: 1. Iterative with Previous Pointer: O(n) time, O(1) space—our best solution. 2. Recursive Approach: O(n) time, O(n) space—an alternative.

Let’s explore the best solution.

Best Solution: Iterative with Previous Pointer Approach

Explanation

The Iterative with Previous Pointer approach uses a dummy node and two pointers:

• A dummy node points to the head to handle cases where the head needs removal.
• A prev pointer tracks the node before the current one.
• A curr pointer iterates through the list.
• If curr.val == val, skip curr by updating prev.next.
• Otherwise, move both pointers forward.

This runs in O(n) time (one pass through the list) and O(1) space (just pointers), making it efficient and straightforward—our best solution.

For [1,2,6,3,4,5,6], val = 6, it removes both 6s seamlessly.

Step-by-Step Example

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

Goal: Return [1,2,3,4,5].

• Step 1: Initialize.
• Dummy node → 1, prev = dummy, curr = 1.
• Step 2: Iterate.
• curr = 1: Not 6, prev = 1, curr = 2.
• curr = 2: Not 6, prev = 2, curr = 6.
• curr = 6: Equals 6, prev.next = 3, curr = 3.
• curr = 3: Not 6, prev = 3, curr = 4.
• curr = 4: Not 6, prev = 4, curr = 5.
• curr = 5: Not 6, prev = 5, curr = 6.
• curr = 6: Equals 6, prev.next = None, curr = None.
• Step 3: Finish.
• List: 1 → 2 → 3 → 4 → 5.
• Output: Return dummy.next (head = 1).

Example 2: head = [7,7,7], val = 7

Goal: Return [].

• Step 1: Dummy → 7, prev = dummy, curr = 7.
• Step 2:
• curr = 7: Equals 7, prev.next = 7, curr = 7.
• curr = 7: Equals 7, prev.next = 7, curr = 7.
• curr = 7: Equals 7, prev.next = None, curr = None.
• Output: dummy.next = None, return [].

How the Code Works (Iterative with Previous Pointer) – Detailed Line-by-Line Explanation

Here’s the Python code with a detailed breakdown (assuming a ListNode class):

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

def removeElements(head: ListNode, val: int) -> ListNode:
    # Line 1: Create dummy node to handle head removal
    dummy = ListNode(0)
    # Dummy node with value 0 (e.g., 0 → head)
    dummy.next = head
    # Link to original head (e.g., 0 → 1)

    # Line 2: Initialize pointers
    prev = dummy
    # Points to dummy (e.g., prev = 0)
    curr = head
    # Points to head (e.g., curr = 1)

    # Line 3: Iterate through the list
    while curr:
        # Continue until end (e.g., curr != None)
        if curr.val == val:
            # If current node matches val (e.g., 6 == 6)
            prev.next = curr.next
            # Skip current (e.g., 2 → 3 instead of 2 → 6)
        else:
            # If no match, move prev forward
            prev = curr
            # Update prev (e.g., prev = 2)
        curr = curr.next
        # Move curr (e.g., curr = 3)

    # Line 4: Return modified list head
    return dummy.next
    # Head of new list (e.g., 1)

This solution handles all cases efficiently.

Alternative: Recursive Approach

Explanation

The Recursive Approach processes the list by:

• Base case: If head is None, return None.
• Recursively process head.next.
• If head.val == val, return the recursive result (skip head).
• Otherwise, link head to the recursive result.

It’s O(n) time (one pass) and O(n) space (recursion stack), offering a clean but less space-efficient alternative.

Step-by-Step Example

For [1,2,6,3], val = 6:

• head = 1: Not 6, recurse on 2.
• head = 2: Not 6, recurse on 6.
• head = 6: Equals 6, return recurse on 3.
• head = 3: Not 6, recurse on None.
• None: Return None.
• Build back: 3 → None, 2 → 3, 1 → 2.
• Output: [1,2,3].

How the Code Works (Recursive)

Copy codedef removeElementsRecursive(head: ListNode, val: int) -> ListNode:
    if not head:
        return None
    head.next = removeElementsRecursive(head.next, val)
    return head.next if head.val == val else head

Complexity

• Iterative with Previous Pointer:
• Time: O(n) – one pass.
• Space: O(1) – just pointers.
• Recursive Approach:
• Time: O(n) – one pass.
• Space: O(n) – recursion stack.

Efficiency Notes

Iterative with Previous Pointer is our best solution with O(1) space and simplicity. Recursive is elegant but uses O(n) space, less ideal for large lists.

Key Insights

• Dummy Node: Simplifies head removal.
• Pointers: Track and adjust links.
• Recursion: Skips nodes naturally.

Additional Example

For [1,1,1], val = 1:

• Iterative: Dummy skips all, returns [].
• Recursive: Skips all, returns None.

Edge Cases

• Empty list: [] → [].
• All match: [6,6], val = 6 → [].
• Head matches: [6,1], val = 6 → [1].

Both handle these well.

Final Thoughts

LeetCode 203: Remove Linked List Elements in Python is a great intro to linked list manipulation. Iterative with Previous Pointer excels in efficiency, while Recursive offers elegance. Want more? Try LeetCode 206: Reverse Linked List or LeetCode 21: Merge Two Sorted Lists. Test your skills—Solve LeetCode 203 on LeetCode with [1,2,6,3,4,5,6], val = 6 (expecting [1,2,3,4,5])—prune those nodes now!