A webhook retry queue is a singly linked list of pending deliveries. Ops wants the nth-from-last retry cancelled — the one that will fire just before the newest — without a second walk to learn the queue length. The intern counted nodes, then walked length - n and unlinked. Correct. Two full passes of a backlog that was already millions of events by the time the on-call ticket landed.

Removing the nth node from the end means unlinking that node and returning the (possibly new) head. The linked list post owns splice, dummy nodes, and why get(i) walks. The two pointers post owns fast/slow as a procedure. Here we only care about a dummy so head-removal is ordinary, and a gap of n so we never count the length.

The problem

Given the head of a singly linked list and an integer n, remove the nth node from the end of the list and return the head. n is 1-based from the tail and is always valid: n = 1 drops the last node; n equal to the length drops the head. The returned head may be a different node, or null if the list had one node.

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

A node is the usual two fields:

final class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

Note: In-place means rewiring next on the predecessor. Copying values into an array, dropping index length - n, and building a fresh chain is a different list — the same identity trap as Reverse Linked List.

Two passes: count, then walk

First walk counts length L. Second walk stops on the predecessor of the victim (L - n from the head, 0-based) and sets pred.next = pred.next.next. If n == L there is no predecessor in the original list — return head.next.

ListNode removeNthFromEndTwoPass(ListNode head, int n) {
    int length = 0;
    for (ListNode p = head; p != null; p = p.next) {
        length++;
    }
    if (n == length) {
        return head.next;
    }
    ListNode pred = head;
    for (int i = 0; i < length - n - 1; i++) {
        pred = pred.next;
    }
    pred.next = pred.next.next;
    return head;
}

The if (n == length) branch is the tell: a dummy would have given that victim a predecessor too. At a handful of retries this is a rounding error. At a million-event queue you paid two full walks for a question a gap of n answers in one: the predecessor of the nth-from-end is a fixed offset behind the tail.

One pass: dummy, then a gap of n

A dummy in front of head gives every victim — including the old head — a predecessor, so head-removal is the same unlink. Fast and slow start at dummy; fast walks n + 1 steps, then both walk until fast is null, and slow sits on the node before the victim. Unlink and return dummy.next.

Walk n = 2 on 1 → 2 → 3 → 4 → 5:

dummy → 1 → 2 → 3 → 4 → 5 → null    n = 2

fast walks n+1 = 3 steps from dummy:
  dummy → 1 → 2 → 3     fast=3, slow=dummy

then both walk until fast is null:
  fast=4, slow=1
  fast=5, slow=2
  fast=null, slow=3

slow sits before the victim (4). unlink: 3.next = 5
return dummy.next (still 1)

Dropping the head is the same walk. n equals the length, so fast falls off the list during the gap setup and the joint walk never runs — slow is still dummy, and dummy.next = dummy.next.next is the new head.

dummy → 1 → 2 → null    n = 2  (drop the head)

fast walks 3 steps: 1, 2, null     fast=null, slow=dummy
joint walk never runs
unlink: dummy.next = 2
return 2

The Java is that walk. Dummy’s val is unused; new ListNode(0) is only a handle.

ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode fast = dummy;
    ListNode slow = dummy;
    for (int i = 0; i < n + 1; i++) {
        fast = fast.next;
    }
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return dummy.next;
}

Time is O(L) — one pass over a list of length L; fast visits each node once. Space is O(1) besides the dummy. Dummy is a bookkeeping node, not a copy of the list; the linked list post already said when sentinels are worth it.

Note: Walk n + 1 from dummy, not n. A gap of n lands slow on the victim, and a singly list cannot unlink a node you only hold. Walking n and then stopping when fast.next is null is the same gap; walking n and stopping when fast is null is not.

What interviewers usually poke next

  • n larger than the length, or n = 0. The prompt promised a valid n. In production you would reject; at the board, ask.
  • Nth from the start. Then you do not need a gap: walk n - 1 from dummy and unlink. Dummy still saves the head case.
  • Middle of the list. Fast takes two steps, slow takes one; they meet in the middle. This prompt is a fixed gap of n, not a 2:1 step ratio. Same two-pointer family on a list; different invariant.
  • Reverse, drop the nth from the new head, reverse back. Correct, three passes, extra rewiring. Reverse Linked List is that rewire; say why the gap is cheaper.
  • Return the removed node, not the new head. Same walk; the victim is slow.next before the unlink.

You are done with this problem when you can unlink the second-from-end of 1 → 2 → 3 → 4 → 5 without counting, and you can drop the head of a one-node list without a special case.