I’ve come across this linked list problem on Leetcode. Having two pointers, fast & slow, on the nodes seems very clever.

The Problem

Given a linked list, remove the nth node from the end and return the head.

Input:  1 → 2 → 3 → 4 → 5,  n = 2
Output: 1 → 2 → 3 → 5

The Code

function removeNthFromEnd($head, $n) {
    $dummyNode = new ListNode(0);
    $dummyNode->next = $head;
    $fast = $dummyNode;
    $slow = $dummyNode;

    // fast pointer moves n nodes at t=0
    for ($i = 0; $i < $n; $i++) {
        $fast = $fast->next;
    }

    // we move both pointers until fast reaches the end
    while ($fast->next !== null) {
        $fast = $fast->next;
        $slow = $slow->next;
    }

    // slow pointer is on the node we'd like to extract
    $slow->next = $slow->next->next;

    return $dummyNode->next;
}

Step 1 — Set up the dummy node

We attach a dummy node before the head. This handles the edge case where we need to remove the head itself. The slow pointer always has a node to land on.

graph LR
    D[dummy\n0] --> N1[1] --> N2[2] --> N3[3] --> N4[4] --> N5[5] --> NULL
    F[fast 👆] -.-> D
    S[slow 👆] -.-> D

Step 2 — Advance fast pointer by N nodes

We move fast forward n = 2 steps. This creates a gap of exactly n nodes between fast and slow pointers.

graph LR
    D[dummy\n0] --> N1[1] --> N2[2] --> N3[3] --> N4[4] --> N5[5] --> NULL
    F[fast 👆] -.-> N2
    S[slow 👆] -.-> D

Step 3 — Advance both pointers until fast->next is null

We move both pointers forward together, preserving the gap, until fast->next is null. This means fast pointer is at the last node.

After 1st move:

graph LR
    D[dummy\n0] --> N1[1] --> N2[2] --> N3[3] --> N4[4] --> N5[5] --> NULL
    F[fast 👆] -.-> N3
    S[slow 👆] -.-> N1

After 2nd move:

graph LR
    D[dummy\n0] --> N1[1] --> N2[2] --> N3[3] --> N4[4] --> N5[5] --> NULL
    F[fast 👆] -.-> N4
    S[slow 👆] -.-> N2

After 3rd move:

graph LR
    D[dummy\n0] --> N1[1] --> N2[2] --> N3[3] --> N4[4] --> N5[5] --> NULL
    F[fast 👆] -.-> N5
    S[slow 👆] -.-> N3

fast->next is now null — we stop. slow is sitting exactly one node before the target (node 4).

Step 4 — Remove the target node

$slow->next = $slow->next->next;

We skip over node 4 by pointing slow->next directly to node 5.

graph LR
    D[dummy\n0] --> N1[1] --> N2[2] --> N3[3] --> N5[5] --> NULL
    N4[4 ❌] -.->|skipped| N5
    S[slow 👆] -.-> N3

Step 5 — Return the result

return $dummyNode->next;

We return dummyNode->next — skipping past the dummy — to get the real head of the modified list.

graph LR
    N1[1] --> N2[2] --> N3[3] --> N5[5] --> NULL

Why the gap works

When fast reaches the last node, the gap between slow and fast is still exactly n. So slow is always pointing at the node just before the one we want to remove.

n fast stops at slow stops at node removed
1 node 5 (last) node 4 node 5
2 node 5 (last) node 3 node 4
5 node 5 (last) dummy node 1 (head)

Complexity

  • Time: O(n) — one pass through the list
  • Space: O(1) — only two pointers and a dummy node, no extra memory