Give one list pointer a head start
Updated
fast walks k nexts first. slow stays at head until the lead is in place. Then they move in lockstep. The gap is k nodes.
What to focus on
k=2 on 4→1→9 puts fast at 9, slow at 4. Lockstep until fast is null lands slow on the k-th from the end.
Worked examples
k=2
a = [4, 1, 9] as 4→1→9, k=2- fast: 4→1→9
- fast at 9, slow at 4
- then both one step: fast null, slow at 1
Result: slow at 1, 2nd from end
k=1
a = [4, 1, 9] as 4→1→9, k=1- fast one step to 1
- lockstep to tail
- slow ends at 9
Result: slow at 9, last node
k=2 on four
a = [4, 1, 9, 1] as 4→1→9→1, k=2- fast two steps to 9
- lockstep: fast to last 1 then null, slow to 9
Result: slow at 9, 2nd from end
Try it
Write nthFromEnd(a, k). a is the start of the list. k is an integer with 1 ≤ k ≤ n. fast gets a head start of k nexts. slow starts at a. Return the k-th node from the end. On 4→1→9, k=2 returns 1 and k=1 returns 9. On 4→1→9→1, k=2 returns 9.
The list is nonempty. 1 ≤ k ≤ n.