4.9.4 — Remove Nth Node From End of List

LeetCode 19 · Medium · ★ Blind 75

The problem

Remove the n-th node counting from the end, and return the head.

1 → 2 → 3 → 4 → 5,  n = 2   →   1 → 2 → 3 → 5
1,                  n = 1   →   (empty list)

n is always valid. The follow-up asks for one pass.

The pattern

Counting from the end is awkward in a singly linked list, because you can only walk forwards. The two-pass answer is easy: count the length, then walk length - n steps and unlink. That is two passes.

The one-pass version uses a gap. Move one pointer n steps ahead, then advance both together. When the leading pointer reaches the end, the trailing one is exactly n from the end — because the distance between them never changes.

n = 2

1 → 2 → 3 → 4 → 5
↑       ↑
slow   fast        (gap of 2)

...both advance until fast falls off the end...

1 → 2 → 3 → 4 → 5
        ↑       ↑
       slow    fast(null)

To delete a node in a singly linked list you need the node before it, so the trailing pointer must stop one short of the target. That is arranged by starting it at a dummy head.

The solution

Python

class Solution:
    def removeNthFromEnd(self, head, n: int):
        dummy = ListNode(0, head)
        slow = fast = dummy

        for _ in range(n):              # open a gap of n
            fast = fast.next

        while fast.next:                # advance until fast is on the last node
            slow = slow.next
            fast = fast.next

        slow.next = slow.next.next      # unlink

        return dummy.next

TypeScript

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dummy = new ListNode(0, head);
  let slow = dummy, fast = dummy;

  for (let i = 0; i < n; i++) fast = fast.next!;

  while (fast.next) {
    slow = slow.next!;
    fast = fast.next;
  }

  slow.next = slow.next!.next;

  return dummy.next;
}

The dummy head is doing real work here, not just tidying. Consider 1, n = 1: the node to remove is the head itself, and there is no previous node to rewire. With a dummy in front, the head has a predecessor like everything else, and dummy.next becomes null — the correct empty list. Without it you need a separate branch for "remove the head".

Both pointers start at dummy, not at head. That is what makes slow land one node before the target rather than on it. If you start them at head, slow ends up on the node to delete and cannot unlink it.

while fast.next rather than while fast. You want fast to stop on the last node, not past it. Advancing one step further would leave slow one node too far along.

Trace

1 → 2 → 3 → 4 → 5, n = 2.

After the gap loop: slow at dummy, fast at node 2.

step	slow	fast
1	1	3
2	2	4
3	3	5

fast.next is null, so stop. slow is on node 3, and slow.next is node 4 — the second from the end. Unlink it: 3 → 5. ✓

Complexity

O(n) time, one pass. O(1) space.

The two-pass version has exactly the same complexity. The one-pass version is not asymptotically better; it matters when the data is a stream you can only read once, which is the real reason the follow-up exists.

Edge cases

• Removing the head — handled by the dummy.
• A single-node list with n = 1 — dummy.next becomes null and the function returns an empty list.
• n equals the list length — the head is removed, same as above.

Try each of these mentally before you say you are done. They are where this problem's bugs live.

Where this goes next

The fixed-gap two pointers idea shows up whenever a problem is phrased relative to the end of a sequence:

• Middle of the Linked List — a gap of half, achieved by moving one pointer twice as fast.
• Linked List Cycle — the same two pointers with different speeds, which is 4.9.7.
• k-th from the end, in any streaming context — log tailing, sliding buffers.

The rule: to reach a position defined from the end in one pass, open a gap and move both pointers together.

What the interviewer will push on

"Why the dummy node?" So that removing the head needs no special case.

"Why do both pointers start at the dummy?" To leave slow one node before the target, since deletion needs the predecessor.

"What if n were larger than the list?" The problem promises it is not. In real code you would check, because the gap loop would dereference null.

"Do it in two passes." Count the length, then walk length - n from a dummy. Say it is the same complexity and only differs for streams.

One thing to volunteer: say what happens when the target is the head, before they ask. That is the edge case this problem is built around.

Next: 4.9.5 Copy List with Random Pointer — a deep copy where the pointers can go anywhere.