ASAPUtils
The invariant
After the initial advance, fast remains exactly n+1 edges ahead of slow. When fast reaches null, slow must be immediately before the node that is n positions from the end.
Optimal one-pass solution
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode dummy(0, head);
ListNode *slow = &dummy, *fast = &dummy;
for (int i = 0; i <= n; ++i) fast = fast->next;
while (fast) {
slow = slow->next;
fast = fast->next;
}
slow->next = slow->next->next;
return dummy.next;
}
function removeNthFromEnd(head, n) {
const dummy = new ListNode(0, head);
let slow = dummy, fast = dummy;
for (let i = 0; i <= n; i++) fast = fast.next;
while (fast) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dummy.next;
}
Why it works
Moving both pointers preserves their gap. The null position is one edge beyond the tail; shifting
back n+1 edges lands on the predecessor of the target. Bypassing slow.next removes exactly one node.
Complexity
Fast traverses at most n list edges and the shared walk is linear: O(length) time. Two pointers and one dummy node use O(1) space.
Alternative
A two-pass solution first counts length L, then deletes position L-n from the front. It is still O(n) time and O(1) space, but the fixed-gap version demonstrates the reusable one-pass pattern.
Traps
- Advancing fast only n edges and landing slow on the target instead of its predecessor.
- Starting at head and needing a special case when n equals the length.
- Returning
headrather thandummy.nextafter the head may have changed. - Assuming invalid n; interview constraints normally guarantee
1 <= n <= length.
Blank re-solve prompt
Draw dummy -> 1 -> 2 -> 3 and remove n=3. If your rule cannot remove 1 without branching, fix the starting point or the gap.