Remove Nth Node From End With a Fixed Gap Walk

"Remove Nth Node From End of List" is a Medium-level staple in Meta, Amazon, Apple loops, and it is a textbook fit for the Fast and Slow Pointers pattern — one of the nine patterns that cover the bulk of what FAANG coding interviews actually test. Part 6 of 11 in the Fast and Slow Pointers arc.

The Problem

Given the head of a linked list, remove the n-th node from the end and return the head. The follow-up that defines the question: do it in a single pass, without first computing the length.

Input:  1 -> 2 -> 3 -> 4 -> 5, n = 2
Output: 1 -> 2 -> 3 -> 5

Recognizing the Fast and Slow Pointers Pattern

Fast and slow pointers (Floyd's tortoise and hare) walk the same structure at different speeds. If there is a cycle they must meet; if there is not, the fast pointer finds the end in half the iterations — which also locates midpoints without knowing the length. It is the default tool for linked lists and for any sequence defined by repeatedly applying a function, all in O(1) space.

K-from-the-end in one pass is the fixed-gap variant of this pattern: two pointers moving at the same speed, separated by n nodes. When the leader hits the end, the trailer sits exactly where you need it.

The Approach

Create a dummy node before the head — deleting the first node then needs no special case, and interviewers specifically watch for this move. Advance the leader n + 1 steps from the dummy, then move both pointers until the leader runs off the end; the trailer now points at the node before the target. Splice it out.

The n + 1 offset (not n) is what parks the trailer one node early — dry-run a two-node list to convince yourself before claiming it.

Python Solution

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


def remove_nth_from_end(head: ListNode | None, n: int) -> ListNode | None:
    """Remove n-th node from the end; single pass, dummy head."""
    dummy = ListNode(0, head)
    lead = trail = dummy
    for _ in range(n + 1):
        lead = lead.next
    while lead:
        lead = lead.next
        trail = trail.next
    trail.next = trail.next.next
    return dummy.next

Complexity

• Time: O(n) — one traversal by the leader
• Space: O(1) — two pointers and a dummy node

Interview Tips and Follow-Ups

• Deleting the head is the planted edge case — the dummy node absorbs it. Skipping the dummy and special-casing is accepted but noted.
• Two-pass (count then delete) is fine as a warm-up; say its downside is a second traversal on a stream-like structure.
• Same fixed-gap walk answers 'find the k-th from the end' and 'split the last k nodes off' — file it as a reusable primitive.

More Fast and Slow Pointers problems — and the other eight patterns — live in the Technical Interview category. Drill the pattern, not the problem: that is the entire thesis of this series.