Why it works
- Every round fast walks two steps and slow one, so fast is always twice as far from the head as slow. When fast runs out of list, slow has covered half of it.
- With an even length fast stops on none, after n / 2 rounds: slow is then on node n / 2 + 1, the second middle. With an odd length fast stops on the last node and slow is on the only middle.
- The length is never counted: one pass, and the loop condition alone decides when to stop.
Complexity
Time O(n): fast walks the list once, two nodes a round, and slow walks half of it. Memory O(1): two pointers.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗