Remove the nth node from the end of a singly linked list in a single pass.

A gap, walked to the end

The two-pass solution is obvious: count the nodes, then walk to the node before position length minus n and unlink. The interviewer asks for one pass to make you find the relationship that removes the counting.

Advance a leader pointer n nodes forward. Then advance the leader and a follower together until the leader runs out of list. The gap between them never changes, so when the leader is off the end, the follower is n nodes back from the end. Which node that is depends precisely on where you stopped the leader, and that is the entire difficulty of the problem.

Off by one, and the node you cannot reach

A singly linked list gives you no way back. To unlink a node you must be holding its predecessor, because the operation is to set the predecessor's next field past the target. So the follower has to land on the predecessor of the nth-from-last node, not on the node itself.

Work out the gap from that requirement rather than by trial. If the leader stops on the null past the last node, and the gap is n, then the follower is n links behind that null. Counting back, n links behind the terminator is the nth node from the end. That lands the follower on the target, which is one node too far. So either start the leader one further forward and stop it on null, or stop the leader on the last node instead of past it, keeping the gap at n. Both give a follower on the predecessor.

Deriving it that way takes ten seconds and it is reliable. Guessing between n and n plus one and then patching until the tests pass is the same amount of work and it does not survive the follow-up question.

The dummy node that deletes the special case

There is still one input the derivation does not cover. If n equals the length of the list, the node to remove is the head, and the head has no predecessor. Any implementation that reasons purely about predecessors has to detect this and branch into a separate "return head.next" path.

A sentinel node placed in front of the head removes the branch entirely. The head now has a predecessor like every other node, and the answer is whatever follows the sentinel at the end. This is not a stylistic preference: it is the difference between one code path and two, and the second path is the one that goes untested.

ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode();          // gives the real head a predecessor
    dummy.next = head;
    ListNode leader = dummy;
    ListNode follower = dummy;

    for (int i = 0; i < n; i++) {
        if (leader.next == null) return head; // n exceeds the length; decide this deliberately
        leader = leader.next;
    }
    while (leader.next != null) {             // stop on the last node, not past it
        leader = leader.next;
        follower = follower.next;
    }
    follower.next = follower.next.next;       // follower is the predecessor by construction
    return dummy.next;                        // not head, which may have just been unlinked
}

The last line matters as much as the unlinking. Returning head would return a node that is no longer in the list when the head was the one removed. Returning dummy.next is correct in every case, which is the point of the sentinel.

Trace it on the two-node list 1 then 2 with n equal to 2. The leader starts at the dummy and advances twice, to node 1 and then node 2. Node 2's next is null, so the while loop never runs and the follower is still the dummy. The dummy's next becomes node 2, and the returned list is just 2. The head was removed with no special case.

What one pass actually bought

Both solutions are O of the list length in time and O of 1 in space. The single-pass version is not asymptotically better, and claiming it is will be corrected. What it gives you is one traversal instead of two, which is worth something when the list does not fit in cache and each hop is a potential miss, and it works on a list you can only read once — a stream of nodes arriving from a source you cannot rewind.

Count the movements if the interviewer presses: the leader makes n moves in the first loop and length minus n in the second, so length in total, and the follower makes length minus n. Each node is visited a bounded number of times and no node is visited twice by the same pointer, which is what "one pass" means here.

The input you should ask about

What should happen when n is larger than the list? There is no nth node from the end, and the reasonable behaviours are to return the list unchanged, to throw, or to treat the input as guaranteed valid because the problem statement said so. All three are defensible and choosing silently is not. The code above returns the list unchanged and says so in a comment, which is the option that fails least destructively if the caller was wrong.

The related question is n equal to zero, which asks to remove the node zero from the end — a node that does not exist. If the interviewer says n is always at least one, say that you are relying on it.