How do you remove the nth node from the end of a linked list in one pass?
Move a fast pointer n steps ahead of a slow pointer, then move both until fast reaches the last node. The slow pointer is then just before the node to delete. A dummy head handles removing the first node.
Explain it simply
You cannot count backwards in a singly linked list, so create a gap instead. Let one runner start n steps ahead of another. When the front runner reaches the end, the back runner is exactly n nodes from the end.
You need the node before the one to delete, so stop the front runner on the last node and keep a dummy node before the head. That way deleting the very first node needs no special case.
Example
class ListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
function fromArray(arr) {
const dummy = new ListNode(0);
let tail = dummy;
for (const v of arr) {
tail.next = new ListNode(v);
tail = tail.next;
}
return dummy.next;
}
function toArray(head) {
const out = [];
while (head) {
out.push(head.val);
head = head.next;
}
return out;
}
function removeNthFromEnd(head, n) {
const dummy = new ListNode(0, head);
let fast = dummy;
let slow = dummy;
for (let i = 0; i < n; i++) fast = fast.next;
while (fast.next) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
console.log(toArray(removeNthFromEnd(fromArray([1, 2, 3, 4, 5]), 2))); // Output: [1,2,3,5]
console.log(toArray(removeNthFromEnd(fromArray([1, 2]), 2))); // Output: [2]Complexity
Time O(n), space O(1).
What to say in the interview
"I put a dummy node before the head, advance fast by n, then move both pointers until fast is on the last node. Slow is then right before the target, so I skip it. This is one pass, O(n) time and O(1) space, and the dummy node handles deleting the head."
Common mistakes
- Not using a dummy node, which breaks when the head itself must be removed.
- Moving fast n + 1 steps in one place and n in another, creating an off-by-one.