dummy
slow
Delete the node that is exactly n positions from the tail in a single pass — no length calculation needed — by keeping a fast pointer n+1 steps ahead of a slow pointer so that when fast hits null, slow lands right before the target.
Given the head of a singly linked list and an integer n, remove the node that is the n-th from the end and return the updated head. Example: list 1→2→3→4→5, n=2 → remove node 4 → return 1→2→3→5. Constraint: n is always valid (1 ≤ n ≤ length).
fast is exactly n+1 nodes ahead of slow, then when fast reaches null (past the last node), slow is sitting on the node just before the one to remove — exactly where you need to relink. One pass, no length needed.dummy.next = head and start both pointers there. The dummy makes “remove the head” just another ordinary unlink — no special case needed.fast exactly n+1 steps. Now there are n+1 nodes between slow and fast.fast === null. The gap stays fixed at n+1, so slow stops on the predecessor of the target.slow.next = slow.next.next removes the target. Return dummy.next.n+1 and not n? You want slow to stop before the node being removed so you can relink. Advancing by only n would leave slow on the target, with no way to splice it out.Both are O(n) time, but the two-pointer approach is a single pass and avoids storing the length. The dummy head is an O(1) allocation that pays back by eliminating all edge-case branches.
[1, 2, 3, 4, 5], remove node 2 from the end. Create a dummy head; both fast and slow start there. The dummy eliminates the edge case of removing the real head.class ListNode {
val: number;
next: ListNode | null;
constructor(val = 0, next: ListNode | null = null) {
this.val = val;
this.next = next;
}
}
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
const dummy = new ListNode(0, head); // dummy head → handles removing the real head
let fast: ListNode | null = dummy;
let slow: ListNode | null = dummy;
// Advance fast n+1 steps so the gap between slow and fast is n+1
for (let i = 0; i <= n; i++) {
fast = fast!.next;
}
// Move both until fast reaches null
while (fast !== null) {
fast = fast.next;
slow = slow!.next;
}
// slow is now just before the node to remove
slow!.next = slow!.next!.next;
return dummy.next;
}new ListNode(0, head) gives us a sentinel node whose next is head. Both pointers start here. When the node to remove is head itself, slow stays on the dummy, and the unlink on line 25 makes the dummy skip the old head — no branch needed.fast exactly n+1 times (loop runs while i <= n) creates a gap of n+1 nodes between slow and fast. After this loop, there are exactly n nodes between them in the list.fast reaches null, slow is exactly at the predecessor of the n-th node from the end. The gap invariant keeps this true for every step.slow.next = slow.next.next bypasses the target node. Because slow is guaranteed non-null (the dummy always precedes it) and slow.next is the target (guaranteed by the constraints), no null checks are needed here.next is the new head — even when the old head was removed.n === length, the head is the target, so return head.next. The dummy collapses that branch.fast n+1 times it falls off the end, n exceeds the list length — throw or return head unchanged.slow.next.val before the unlink and return a tuple [newHead, removedVal].prev pointers, but the two-pointer positioning is identical.| "remove k-th / n-th from the end" | two pointers, gap = n+1 |
| "single pass, no length" | fast/slow with fixed offset |
| "removing the head is an edge case" | dummy head sentinel |
| "find the predecessor to unlink" | stop slow one node early (gap n+1 not n) |
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
const dummy = new ListNode(0, head);
let fast: ListNode | null = dummy;
let slow: ListNode | null = dummy;
for (let i = 0; i <= n; i++) fast = fast!.next;
while (fast !== null) {
fast = fast.next;
slow = slow!.next;
}
slow!.next = slow!.next!.next;
return dummy.next;
}slow to stop on the predecessor of the target so you can relink. A gap of n+1 achieves this; a gap of n would leave slow on the target itself.[1, 2, 3, 4, 5], n=2. Which node is removed and what is the result?new ListNode(0, head))?[1], n=1. What does the function return?