LeetCode 203: Remove Linked List Elements

Problem Restatement

We are given the head of a singly linked list and an integer val.

We need to remove every node whose value equals val.

Return the new head of the linked list after all removals.

The official statement says: given the head of a linked list and an integer val, remove all the nodes of the linked list that have Node.val == val, and return the new head.

Input and Output

Typical node definition:

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

Example function shape:

def removeElements(head: ListNode, val: int) -> ListNode:
    ...

Examples

Example 1:

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

Remove every 6.

Result:

[1,2,3,4,5]

Example 2:

head = []
val = 1

The list is already empty.

Result:

[]

Example 3:

head = [7,7,7,7]
val = 7

Every node must be removed.

Result:

[]

Understanding Linked List Removal

Suppose we have:

1 -> 2 -> 6 -> 3

We want to remove 6.

The node before 6 is 2.

Instead of pointing to 6, node 2 should point directly to 3.

Before:

2 -> 6 -> 3

After:

2 -> 3

So linked list deletion works by changing pointers.

First Thought

We can walk through the list node by node.

For each node:

• If the next node should be removed, skip it.
• Otherwise, move forward.

The main difficulty is removing the head node.

For example:

6 -> 1 -> 2

If we remove the first node, the head changes.

Handling this separately creates extra edge cases.

Key Insight: Use a Dummy Node

A dummy node is a fake node placed before the real head.

Example:

dummy -> 1 -> 2 -> 6 -> 3

Now every real node has a previous node, even the original head.

This makes removal logic uniform.

If the head must be removed, we simply update:

dummy.next

instead of handling a special case.

Algorithm

1. Create a dummy node.
2. Point the dummy node to the original head.
3. Use a pointer called current.
4. While current.next exists:
   • If current.next.val == val, skip that node.
   • Otherwise, move current forward.
5. Return dummy.next.

Walkthrough

Use:

1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6
val = 6

Initial structure:

dummy -> 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6

Start with:

current = dummy

Move through the list.

When current points to node 2:

2 -> 6 -> 3

The next node has value 6, so skip it:

current.next = current.next.next

Now:

2 -> 3

Continue scanning.

Near the end:

5 -> 6

Skip the final 6.

Final list:

1 -> 2 -> 3 -> 4 -> 5

Return:

dummy.next

Correctness

The algorithm maintains the invariant that all nodes before current are already correctly processed.

At each step, the algorithm examines current.next.

If current.next.val == val, that node must be removed. The assignment:

current.next = current.next.next

removes the node from the linked list by bypassing it.

No valid nodes are lost, because the remaining part of the list stays connected.

If current.next.val != val, the node should remain in the list, so the algorithm advances:

current = current.next

The loop continues until every node has been examined.

The dummy node guarantees that even if the original head must be removed, the list remains correctly connected and accessible through:

dummy.next

Therefore, every node with value val is removed, and every other node remains in the final list.

Complexity

Implementation

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head

        current = dummy

        while current.next:
            if current.next.val == val:
                current.next = current.next.next
            else:
                current = current.next

        return dummy.next

Code Explanation

Create a dummy node:

dummy = ListNode(0)
dummy.next = head

Now every node has a previous node.

Start scanning from the dummy node:

current = dummy

Continue while there is a next node:

while current.next:

If the next node should be removed:

if current.next.val == val:

skip it:

current.next = current.next.next

Otherwise move forward:

current = current.next

Finally return the real head:

return dummy.next

Recursive Solution

We can also solve the problem recursively.

Process the rest of the list first, then decide whether to keep the current node.

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        if not head:
            return None

        head.next = self.removeElements(head.next, val)

        if head.val == val:
            return head.next

        return head

Idea:

1. Recursively clean the remaining list.
2. If the current node should be removed, return the cleaned remainder.
3. Otherwise return the current node.

The iterative dummy-node solution is usually preferred in interviews because it avoids recursion depth concerns.

Testing

def build_list(values):
    dummy = ListNode(0)
    current = dummy

    for value in values:
        current.next = ListNode(value)
        current = current.next

    return dummy.next

def to_list(head):
    result = []

    while head:
        result.append(head.val)
        head = head.next

    return result

def run_tests():
    s = Solution()

    head = build_list([1,2,6,3,4,5,6])
    assert to_list(s.removeElements(head, 6)) == [1,2,3,4,5]

    head = build_list([])
    assert to_list(s.removeElements(head, 1)) == []

    head = build_list([7,7,7,7])
    assert to_list(s.removeElements(head, 7)) == []

    head = build_list([1,2,3])
    assert to_list(s.removeElements(head, 4)) == [1,2,3]

    head = build_list([6,1,2])
    assert to_list(s.removeElements(head, 6)) == [1,2]

    print("all tests passed")

run_tests()