Remove the nth node counting from the end of a singly linked list, in one pass (e.g. remove the 2nd from end of 1->2->3->4->5 gives 1->2->3->5).
Advance a fast pointer n nodes ahead, then move fast and slow together until fast reaches the end; slow now sits just before the target, so relink past it. A dummy head handles removing the actual head cleanly. O(n) time, single pass.
public static Node removeNthFromEnd(Node head, int n) {
Node dummy = new Node(0); dummy.next = head;
Node fast = dummy, slow = dummy;
for (int i = 0; i < n; i++) fast = fast.next;
while (fast.next != null) { fast = fast.next; slow = slow.next; }
slow.next = slow.next.next;
return dummy.next;
}function removeNthFromEnd(head, n) {
const dummy = new Node(0); dummy.next = head;
let fast = dummy, 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;
}def remove_nth_from_end(head, n):
dummy = Node(0)
dummy.next = head
fast = slow = dummy
for _ in range(n):
fast = fast.next
while fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.nextThe fixed-gap two-pointer trick is a reusable way to locate a position relative to the end without knowing the length in advance.
Removing the 5th-from-end of a 5-node list (i.e. the head) crashes a naive solution. How does the dummy node help?