# LeetCode 19: Remove Nth Node From End of List

## Problem Restatement

We are given the head of a linked list and an integer `n`.

We need to remove the `n`th node from the end of the list and return the head of the modified list.

The follow-up asks whether we can solve it in one pass. The constraints say the list size is `sz`, where `1 <= sz <= 30`, node values are between `0` and `100`, and `1 <= n <= sz`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Head of a singly linked list and integer `n` |
| Output | Head of the linked list after removing the target node |
| Target | The `n`th node from the end |
| Constraint | `1 <= n <= list size` |
| Follow-up | Solve in one pass |

Example function shape:

```python
def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
    ...
```

## Examples

Example 1:

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

The second node from the end is:

```text
4
```

Remove it:

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

Output:

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

Example 2:

```text
head = [1]
n = 1
```

The only node is also the first node from the end.

After removing it:

```text
[]
```

Output:

```text
[]
```

Example 3:

```text
head = [1, 2]
n = 1
```

The first node from the end is:

```text
2
```

Remove it:

```text
[1]
```

Output:

```text
[1]
```

## First Thought: Count the Length

The direct solution is to count the number of nodes first.

Suppose the list length is `length`.

The `n`th node from the end is the:

```text
length - n
```

index from the start, using zero-based indexing.

For example:

```text
head = [1, 2, 3, 4, 5]
n = 2
length = 5
```

The index to remove is:

```text
5 - 2 = 3
```

Index `3` contains value `4`.

Code:

```python
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)

        length = 0
        current = head

        while current:
            length += 1
            current = current.next

        steps = length - n
        current = dummy

        for _ in range(steps):
            current = current.next

        current.next = current.next.next

        return dummy.next
```

This works, but it uses two passes: one pass to count length, then another pass to remove the node.

## Key Insight

Use two pointers with a fixed gap of `n`.

Create two pointers:

```text
fast
slow
```

Move `fast` ahead by `n` nodes.

Then move both `fast` and `slow` together.

When `fast` reaches the end, `slow` will be right before the node we need to remove.

A dummy node helps because the node to remove may be the head.

Without a dummy node, removing the first node needs special handling.

With a dummy node, every removal looks like:

```python
slow.next = slow.next.next
```

## Visual Walkthrough

Use:

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

Add a dummy node:

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

Start both pointers at `dummy`:

```text
fast = dummy
slow = dummy
```

Move `fast` ahead by `2` nodes:

```text
dummy -> 1 -> 2 -> 3 -> 4 -> 5
              ^
             fast

^
slow
```

Now move both together until `fast.next` is `None`.

Step 1:

```text
dummy -> 1 -> 2 -> 3 -> 4 -> 5
                   ^
                  fast
     ^
    slow
```

Step 2:

```text
dummy -> 1 -> 2 -> 3 -> 4 -> 5
                        ^
                       fast
          ^
         slow
```

Step 3:

```text
dummy -> 1 -> 2 -> 3 -> 4 -> 5
                             ^
                            fast
               ^
              slow
```

Now `fast` is at the last node.

`slow.next` is the node to remove:

```text
4
```

Remove it:

```text
slow.next = slow.next.next
```

Result:

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

## Algorithm

1. Create a dummy node whose `next` points to `head`.
2. Set both `fast` and `slow` to `dummy`.
3. Move `fast` forward `n` times.
4. Move both pointers forward while `fast.next` exists.
5. Now `slow.next` is the target node.
6. Remove it by linking around it.
7. Return `dummy.next`.

## Correctness

After moving `fast` forward `n` times, there are exactly `n` nodes between `slow` and `fast` in the linked list traversal order.

Then both pointers move together one node at a time, preserving this gap.

When `fast` reaches the last node, `slow` is exactly one node before the `n`th node from the end.

So `slow.next` is the node that must be removed.

The assignment:

```python
slow.next = slow.next.next
```

removes exactly that node while preserving the rest of the list.

The dummy node guarantees this also works when the removed node is the original head.

Therefore the algorithm returns the correct modified list.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(sz)` | Each pointer moves through the list at most once |
| Space | `O(1)` | Only a few pointers are stored |

Here `sz` is the number of nodes in the list.

## Implementation

```python
from typing import Optional

class ListNode:
    def __init__(self, val: int = 0, next: Optional["ListNode"] = None):
        self.val = val
        self.next = next

class Solution:
    def removeNthFromEnd(
        self,
        head: Optional[ListNode],
        n: int
    ) -> Optional[ListNode]:
        dummy = ListNode(0, head)

        fast = dummy
        slow = dummy

        for _ in range(n):
            fast = fast.next

        while fast.next:
            fast = fast.next
            slow = slow.next

        slow.next = slow.next.next

        return dummy.next
```

## Code Explanation

Create a dummy node:

```python
dummy = ListNode(0, head)
```

This handles removal of the head node.

Initialize both pointers:

```python
fast = dummy
slow = dummy
```

Move `fast` ahead by `n` nodes:

```python
for _ in range(n):
    fast = fast.next
```

Move both pointers until `fast` reaches the last node:

```python
while fast.next:
    fast = fast.next
    slow = slow.next
```

Now `slow.next` is the node to remove.

Remove it:

```python
slow.next = slow.next.next
```

Return the real head:

```python
return dummy.next
```

## Testing

```python
def build_list(values):
    dummy = ListNode()
    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, 3, 4, 5])
    assert to_list(s.removeNthFromEnd(head, 2)) == [1, 2, 3, 5]

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

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

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

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

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[1, 2, 3, 4, 5]`, `n = 2` | Standard middle removal |
| `[1]`, `n = 1` | Remove only node |
| `[1, 2]`, `n = 1` | Remove tail |
| `[1, 2]`, `n = 2` | Remove head |
| `[1, 2, 3]`, `n = 3` | Head removal with longer list |