Remove Nth Node from End

Before we start

Removing the Nth node from the end requires knowing where the end is — but in a linked list, you can't look backward. The naive solution counts the length first, then removes. The elegant solution finds the target node in a single pass using two pointers with a fixed gap between them. By the end you will be able to:

• Explain the N-gap trick intuitively, not just mechanically.
• Write the solution with a dummy node to handle the edge case where the head itself is removed.
• Recognise the general "gap between two pointers" idea in other problems.

Picture this first (no code yet)

First, the slow way (so you feel the pain)

Two-pass approach: traverse once to count length L, then traverse again to the (L − N)th node, then delete the next node.

def removeNthFromEnd_twopass(head, n):
    length = 0
    node = head
    while node:
        length += 1
        node = node.next
    # second pass: walk to position (length - n)
    dummy = ListNode(0); dummy.next = head
    node = dummy
    for _ in range(length - n):
        node = node.next
    node.next = node.next.next
    return dummy.next

Correct, but two passes over the list. For a list of 10 million nodes that is 20 million steps. The one-pass approach does it in 10 million steps — the same asymptotic class (O(n)) but half the constant.

The turning point

The one idea to remember

The code, line by line

def removeNthFromEnd(head, n: int):
    dummy      = ListNode(0)   # dummy handles the case where head itself is removed
    dummy.next = head
    slow = fast = dummy        # both start at dummy (not head)

    # Step 1: advance fast N+1 steps (N+1 because both start at dummy, not head)
    for _ in range(n + 1):
        fast = fast.next

    # Step 2: walk both until fast is None (off the end)
    while fast:
        slow = slow.next
        fast = fast.next

    # Step 3: delete slow.next
    slow.next = slow.next.next

    return dummy.next

Why N+1 steps, not N? Both start at the dummy (position 0). We want slow to stop at the node before the target — not at the target itself. That requires one extra step of separation so that when fast is at None, slow is at the predecessor.

Alternative phrasing: advance fast N steps from the head (fast = head), then while fast.next: slow = slow.next; fast = fast.next — then slow lands at the node before the target. Both approaches work; use whichever you find clearer.

Watch it happen, frame by frame

List: 1 → 2 → 3 → 4 → 5, n=2

dummy → 1 → 2 → 3 → 4 → 5 → None

Step 1: advance fast N+1=3 steps from dummy:
  fast: dummy → 1 → 2 → 3

  slow=dummy, fast=node3

Step 2: walk both until fast=None:
  Iter 1: slow=node1, fast=node4
  Iter 2: slow=node2, fast=node5
  Iter 3: slow=node3, fast=None → stop

Step 3: slow=node3. slow.next=node4 (the 2nd from end).
  slow.next = slow.next.next = node5.

Result: dummy → 1 → 2 → 3 → 5 → None  ✅

Edge case: n = 5 (remove the head, node 1)

dummy → 1 → 2 → 3 → 4 → 5 → None

Step 1: advance fast 6 steps from dummy:
  dummy → 1 → 2 → 3 → 4 → 5 → None
  After 6 steps: fast = None

Step 2: fast is already None → while loop doesn't execute. slow = dummy.

Step 3: slow.next = node1 (the head). slow.next = slow.next.next = node2.

Result: dummy → 2 → 3 → 4 → 5 → None  ✅
Return dummy.next = node2 (new head).

Without the dummy node, removing the head would require special-casing if slow == dummy: return head.next. The dummy absorbs this edge case cleanly.

The general N-gap idea

This "fixed gap between two pointers" technique appears in several forms:

Common traps

dummy = ListNode(0);  dummy.next = head
slow = fast = dummy

# advance fast N+1 steps (from dummy)
for _ in range(n + 1):
    fast = fast.next

# walk both until fast = None
while fast:
    slow = slow.next
    fast = fast.next

# delete slow.next
slow.next = slow.next.next
return dummy.next

Check yourself

Practice problems

This completes the first half of Chapter 4 — Linked Lists. Next up: Intersection of Two Linked Lists — the elegant "reset to the other list's head" trick that finds the intersection node in O(n + m) time, O(1) space.