Remove Nth Node From End

Concept

Problem: Given the head of a linked list, remove the n-th node from the end of the list and return its head.

If this were an Array, it would be trivial: array.length - n.
If this were a Doubly Linked List, we could start at the Tail and walk backwards n steps.
But in a Singly Linked List, we can only walk forward, and we don’t know the length.

The Two-Pass Solution:

1. Walk the entire list to count the total nodes (length).
2. Calculate the target index from the front: target = length - n.
3. Walk the list a second time, stop right before the target, and rewire the pointer to skip it.
   (This is a perfectly acceptable $O(N)$ solution, but interviewers will ask: “Can you do it in one pass?”)

The One-Pass Solution: The Delayed Pointer

To do this in a single pass, we use a variation of Two Pointers.
We create a Fast pointer and a Slow pointer.

The Trick: Give the Fast pointer a head start of exactly N steps.
If N = 2, we move Fast forward 2 times.
Then, we move both pointers forward at the exact same speed (1 step at a time).
Because Fast is exactly 2 steps ahead of Slow, when Fast physically hits the end of the list, Slow is guaranteed to be sitting exactly 2 steps behind the end!

Implementation

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    // The Dummy Node is CRITICAL here. 
    // What if N = the length of the list? (We need to delete the true Head).
    // The Dummy Node prevents edge-case crashes.
    const dummy = new ListNode(0);
    dummy.next = head;
    
    let slow: ListNode | null = dummy;
    let fast: ListNode | null = dummy;

    // 1. Give Fast a head start of N steps
    // (We actually want Fast to be N + 1 steps ahead, so Slow lands 
    // exactly on the node right BEFORE the target node, allowing us to delete it)
    for (let i = 0; i <= n; i++) {
        fast = fast!.next;
    }

    // 2. Move both at the same speed until Fast falls off the end
    while (fast !== null) {
        slow = slow!.next;
        fast = fast.next;
    }

    // 3. Fast hit the end. Slow is right before the target. Delete the target!
    slow!.next = slow!.next!.next;

    return dummy.next;
}

Interview Questions

Q: A developer writes the Two-Pass solution (counting the length first). You wrote the One-Pass solution. The developer argues: “My solution iterates N times, then N-K times. Yours iterates K times, then N-K times simultaneously. We both touch roughly the same number of nodes. Is yours actually faster?”
A: Theoretically, no. Both solutions have the exact same Big-O time complexity: $O(N)$.
In fact, the developer’s Two-Pass solution might actually execute marginally faster on modern CPUs due to CPU cache locality (doing one fast, uninterrupted count loop, followed by one fast traversal loop).
The One-Pass solution is technically a “trick”. However, in an interview, implementing the One-Pass Delayed Pointer proves a higher level of algorithmic mastery and pointer manipulation, which is what the interviewer is actually testing for.

Q: Why do we use the dummy node in this specific problem?
A: Imagine the list is [1] and we want to remove the 1st node from the end (so, we want to delete node 1).
If we don’t use a Dummy node, both Slow and Fast start at node 1. Fast moves 1 step and hits null. We want to delete Slow, but because it’s the absolute Head, we can’t do slow.next = slow.next.next (it crashes). We would have to write a custom if statement for this edge case.
By starting Slow and Fast on the Dummy Node, the math works out perfectly so that Slow lands on the Dummy Node itself, and we just do dummy.next = dummy.next.next, which elegantly updates the true Head of the list to null.