Q35: Remove Nth Node From End of List
Given the head of a linked list, remove the $n$-th node from the end of the list and return its head in a single pass.
Two-Pointer Offset Node Removal
function removeNthFromEnd(head, n) {
const dummy = { val: 0, next: head };
let fast = dummy;
let slow = dummy;
// Advance fast pointer n steps ahead
for (let i = 0; i <= n; i++) {
fast = fast.next;
}
// Move fast and slow together until fast reaches end
while (fast !== null) {
fast = fast.next;
slow = slow.next;
}
// Remove target node
slow.next = slow.next.next;
return dummy.next;
}💡 Advances
fast $n+1$ steps ahead. Moving both pointers at equal speed keeps slow exactly $n$ steps behind fast. When fast reaches null, slow.next = slow.next.next deletes target.Key Takeaways
- Use Two Pointers (
fastandslow) offset by $n$ steps. - When
fastreaches the list end,slowpoints directly before the target node to delete.
Knowledge Check
Why is a dummy node initialized before the head of the linked list?