An interactive visualization of the two-pointer gap technique on a linked list. Watch how a fast pointer races ahead by n+1 steps, then both pointers advance together until fast reaches the end, leaving slow right before the node to remove.
Linked List LeetCode 19 ↗ Mediumhead of a linked list, remove the nth node from the end of the list and return its head.1 → 2 → 3 → 4 → 5 and n = 2, the 2nd node from the end is 4.
After removing it, the list becomes 1 → 2 → 3 → 5.fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? { val dummy = ListNode(0).also { it.next = head } var fast: ListNode? = dummy var slow: ListNode? = dummy for (i in 0....n) { // advance fast n+1 ahead fast = fast?.next } while (fast != null) { // move both until fast hits null fast = fast?.next slow = slow?.next } slow?.next = slow?.next?.next // skip the target return dummy.next }
To find the nth node from the end in a single pass, we use a two-pointer gap technique.
If we maintain a gap of exactly n + 1 between a fast pointer and a slow pointer,
then when fast reaches the end (null), slow will be pointing to the node just before the target node.
This lets us simply unlink the target by setting slow.next = slow.next.next.
head. This handles the edge case where the head itself needs to be removed.fast by n + 1 steps from dummy. Now there is a gap of n + 1 nodes between fast and slow.fast and slow one step at a time until fast is null.slow is now right before the target node. Set slow.next = slow.next.next to skip over it.dummy.next (the new head of the list).We traverse the list once with the fast pointer and once (partially) with the slow pointer, giving linear time. Only a constant number of extra pointers are used — no auxiliary data structures needed.