Given the head of a linked list, remove the nth node from the end of the list and return its head.
head = [1,2,3,4,5], n = 2[1,2,3,5]head = [1], n = 1[]head = [1,2], n = 1[1]dummy node before head; set both fast and slow to dummyfast exactly n+1 steps to establish a gap of n+1fast and slow together until fast == nullslow.next is the target node; bypass it: slow.next = slow.next.nextdummy.next (handles head-removal edge case)
When fast is n+1 ahead of slow and they move in lockstep,
the moment fast falls off the end (null), slow sits exactly
at the node before the one we want to delete. The dummy node means we never
have to special-case removing the head — slow's .next is always the real target.
Counting the length, then walking to length minus n, takes two passes. A fixed gap between two pointers does it in one.
Add a dummy node before the head, so removing the head is not a special case. Move fast n plus 1 steps ahead of slow. Then move both until fast falls off the end, and slow sits just before the target.
A gap of n between two pointers finds the n-th from the end. A dummy head removes the edge case of deleting the first node.
Run the animation above on your own input, or watch the 1:15 video explanation of Remove Nth Node From End of List with a dry run and Java code.