# 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

| Item | Meaning |
|---|---|
| Input | Head of a singly linked list and integer `val` |
| Output | Head of the modified linked list |
| Goal | Remove every node whose value equals `val` |
| Important case | The head itself may need to be removed |

Typical node definition:

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

Example function shape:

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

## Examples

Example 1:

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

Remove every `6`.

Result:

```text
[1,2,3,4,5]
```

Example 2:

```text
head = []
val = 1
```

The list is already empty.

Result:

```text
[]
```

Example 3:

```text
head = [7,7,7,7]
val = 7
```

Every node must be removed.

Result:

```text
[]
```

## Understanding Linked List Removal

Suppose we have:

```text
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:

```text
2 -> 6 -> 3
```

After:

```text
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:

```text
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:

```text
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:

```python
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:

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

Initial structure:

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

Start with:

```python
current = dummy
```

Move through the list.

When `current` points to node `2`:

```text
2 -> 6 -> 3
```

The next node has value `6`, so skip it:

```python
current.next = current.next.next
```

Now:

```text
2 -> 3
```

Continue scanning.

Near the end:

```text
5 -> 6
```

Skip the final `6`.

Final list:

```text
1 -> 2 -> 3 -> 4 -> 5
```

Return:

```python
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:

```python
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:

```python
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:

```python
dummy.next
```

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

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each node is visited at most once |
| Space | `O(1)` | Only a few pointers are used |

## Implementation

```python
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:

```python
dummy = ListNode(0)
dummy.next = head
```

Now every node has a previous node.

Start scanning from the dummy node:

```python
current = dummy
```

Continue while there is a next node:

```python
while current.next:
```

If the next node should be removed:

```python
if current.next.val == val:
```

skip it:

```python
current.next = current.next.next
```

Otherwise move forward:

```python
current = current.next
```

Finally return the real head:

```python
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.

```python
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

```python
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()
```

| Test | Why |
|---|---|
| `[1,2,6,3,4,5,6]` | Standard mixed removals |
| `[]` | Empty list |
| `[7,7,7,7]` | Remove every node |
| `[1,2,3]` with `4` | No removals |
| `[6,1,2]` | Head removal case |