Remove Nth Node From End of List

1. Problem & Core Objective

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

head = [1,2,3,4,5], n = 2   →   [1,2,3,5]
head = [1],         n = 1   →   []

Constraints: 1 <= size <= 30 · 1 <= n <= size (so n is always valid)

What's actually being tested: the fixed-gap two-pointer idiom — converting a position-from-the-end into a position-from-the-start without measuring the list. Plus the dummy head, because removing the first node is the edge case that breaks naive solutions.

2. First-Principles Thought Process

Why "from the end" is awkward

To remove a node you need the node before it, so you can set prev.next = prev.next.next. Finding a node counted from the start is easy. Counting from the end means you must first know the length — which is a full pass.

Two passes obviously work. The interesting question is whether one is enough.

Converting end-relative into start-relative

Here's the trick. Put two pointers on the list with a gap of exactly n between them, then slide them forward together. The gap never changes. So when the leading pointer reaches the end, the trailing one is exactly n from the end.

The gap is doing the counting for you — you never learn the length, you just preserve a distance.

The edge case that breaks it

What if the node to remove is the head itself? Then there's no "previous node" to rewire, and you need a separate branch:

if (removingHead) head = head.next;
else              prev.next = prev.next.next;

The dummy head kills this. Start slow at a dummy node that sits before head. Now every real node has a predecessor, including the first one, and dummy.next gives the possibly-changed head back.

This is the second appearance of the dummy in this section, and it's exactly the same reason: make the special case stop being special.

3. Solution Paths

Approach 1 — Count the length, then walk again (brute force)

public ListNode removeNthFromEnd(ListNode head, int n) {
    int length = 0;
    for (ListNode p = head; p != null; p = p.next) length++;

    if (length == n) return head.next;            // removing the head

    ListNode prev = head;
    for (int i = 0; i < length - n - 1; i++) prev = prev.next;
    prev.next = prev.next.next;
    return head;
}

Measure, convert n-from-the-end into length - n from the start, walk there.

• Time O(L) — two passes · Space O(1)

Counter-questions on this approach

⭐ "Two passes is still O(n). Is the one-pass version actually better?"

Asymptotically, no — both are O(L), and for an in-memory list the difference is a constant factor. I'd say that honestly rather than overselling it.

Where it genuinely matters is when you can't re-read the input: a stream, a network cursor, a database iterator you can only advance once. Then two passes isn't a constant factor worse, it's impossible. The one-pass version is what generalizes.

⭐ "What is the if (length == n) line for?"

Removing the head. length - n - 1 would be -1, so the walk loop can't position prev before the first node — there is no node before it. That branch is the special case, and it's exactly what the dummy head removes in the next approach.

"Off-by-one check: why length - n - 1 and not length - n?"

Because I need the node before the victim. The victim is at 0-based index length - n, so its predecessor is at length - n - 1. Getting this wrong deletes the neighbour, and it still returns a plausible-looking list — which is why I'd trace [1,2,3,4,5], n = 2 explicitly: length 5, victim index 3 (value 4), predecessor index 2 (value 3). ✓

Approach 2 — Two pointers with a fixed gap and a dummy (optimal)

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);
    ListNode slow = dummy, fast = dummy;

    for (int i = 0; i < n; i++) fast = fast.next;   // open a gap of n

    while (fast.next != null) {                     // slide until fast is on the last node
        slow = slow.next;
        fast = fast.next;
    }

    slow.next = slow.next.next;                     // slow is the victim's predecessor
    return dummy.next;
}

Trace — [1,2,3,4,5], n = 2:

• Time O(L) — one pass · Space O(1)

Counter-questions on this approach

⭐ "Why does the loop test fast.next != null rather than fast != null?"

Because I need slow to stop on the victim's predecessor, not on the victim. Stopping when fast runs off the end entirely would put slow one node too far, and slow.next = slow.next.next would then delete the wrong node — or throw, if the victim was last.

Stopping while fast is still on the last node leaves slow exactly one before the target.

⭐ "Why start both pointers at the dummy instead of at head?"

So that removing the head needs no special case. With both starting at dummy, the gap is measured from a node that sits before the list, which means slow can legitimately end up on the dummy — and that's precisely the case where the victim is the head. slow.next = slow.next.next then sets dummy.next to the second node, and return dummy.next hands back the new head.

Starting at head instead, slow could never land before the first node, so removing it would need its own branch.

"Show me that with [1], n = 1."

dummy → 1. Open the gap: fast advances once, to node 1. The while loop checks fast.next — it's null, so the loop never runs and slow stays on the dummy. Then slow.next = slow.next.next sets dummy.next = null. Return dummy.next → null, the empty list. ✓ No branch anywhere.

"Can fast run off the end while opening the gap?"

Not given the constraint n <= size. If n could exceed the size, fast = fast.next would throw a NullPointerException on the n-th step, and I'd add a guard returning head unchanged. Worth asking about rather than assuming — the constraint is doing real work here.

"Is the gap really n, or n+1?"

fast is n nodes ahead of slow. Since slow starts one before the list, being n ahead of slow puts fast n-1 nodes into the list. When fast stops on the last node, slow is n nodes before the end — which is the predecessor of the n-th from the end. The dummy is what makes n rather than n+1 the right gap.

Comparison

4. Why the Optimal Wins

The two solutions have identical complexity. The one-pass version wins on two counts that aren't asymptotic:

It generalizes to streams. If the input can only be traversed once — a socket, a cursor, a generator — the two-pass version simply doesn't work. The gap technique needs only a bounded window of the sequence in hand at any moment.

It has no special cases. The dummy makes head-removal ordinary, so there are no branches to get wrong. The two-pass version has an if that exists solely to handle one input shape, and untested branches are where bugs live.

The framing worth keeping:

To find something n from the end in one pass, open a gap of n and slide it. The gap does the counting.

This is the same idea as the sliding window in Section 3 — a fixed-width window dragged across a sequence — applied to a list.

5. Java Prerequisites

Dummy with an initial next

ListNode dummy = new ListNode(0, head);   // the two-arg constructor

Opening a fixed gap

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

Deleting the node after slow

slow.next = slow.next.next;

Java's GC reclaims the orphan; in C you would free it here.

Stop conditions — know the difference

while (fast != null)        // walks off the end; slow ends ON the victim
while (fast.next != null)   // stops on the last node; slow ends BEFORE it

Almost every bug in this problem is choosing the wrong one of these two.

6. Interview Communication Guide

Clarifying questions: Is n guaranteed valid (yes, 1 <= n <= size)? Can the list become empty (yes — [1] with n = 1)? Is one pass required, or is two acceptable (ask; it changes what I write)? Should I return the head or mutate in place (return, since the head may change)?

The pitch

"Removing a node needs its predecessor, and counting from the end normally means measuring the list first — a second pass.

I can avoid that with a fixed gap. Put two pointers n apart and slide them together. The gap never changes, so when the leading one reaches the last node, the trailing one is exactly n from the end — sitting on the victim's predecessor. I never learn the length; I just preserve a distance.

The nasty case is removing the head, because it has no predecessor. So I start both pointers at a dummy node placed before the head. Now every node including the first has something in front of it, slow can legitimately end up on the dummy, and return dummy.next hands back the head whether or not it changed.

One detail: the slide loop tests fast.next != null, not fast != null — I want to stop while fast is still on the last node, so slow lands one before the target rather than on it.

One pass, O(L) time, O(1) space, and no branches."

Edge cases to volunteer:

Name [1,2] with n = 2. It's the head-removal case, it's what the dummy exists for, and a solution without a dummy will either throw or return the wrong list there.

7. Follow-Up Questions — Modified Constraints

⭐ "What if n could be larger than the list?"

fast would hit null while opening the gap and throw. I'd guard the loop — for (int i = 0; i < n && fast != null; i++) — and return head unchanged if fast came out null, meaning there is no n-th node from the end. Worth handling explicitly rather than relying on a constraint the caller might not honour.

⭐ "Remove ALL nodes that are n from the end of some suffix — i.e. deduplicate by position."

The gap trick doesn't extend; it finds one position. You'd fall back to indexing, or reframe the requirement. Saying plainly that a technique doesn't generalize is better than forcing it.

"Return the n-th node from the end instead of removing it."

Same gap, but slide with while (fast != null) so slow lands on the node rather than before it — and you no longer need the dummy, since you're not rewiring anything. The one-character change in the loop condition is the whole difference.

"What if it were a doubly linked list?"

Walk backwards from the tail n steps. O(n) instead of O(L), and no gap needed — the back-pointers already give end-relative access. Deletion is also local: node.prev.next = node.next; node.next.prev = node.prev.

"What if the list were a read-once stream?"

This is exactly where the one-pass version is the only option. Keep a ring buffer of the last n+1 elements as you consume the stream; when it ends, the buffer's oldest entry is the predecessor of the n-th from the end. Same idea as the gap, made explicit as storage.

"Remove the middle node instead."

Slow/fast with fast moving twice as fast — slow lands on the middle. Same family of technique: a ratio between the pointers rather than a fixed gap. Worth noting the two variants together, since they look similar and solve different problems.