Why it works
- If the list ends, fast gets to none first and the loop stops: false. The check of fast and fast.next comes first, so fast.next.next is never taken from none.
- If the list loops, both pointers end up going round the loop. Each round fast walks two steps and slow one, so the gap between them shrinks by exactly one: fast cannot jump over slow, it lands on it.
- «slow is fast» compares nodes, not values: two different nodes may hold the same number.
Complexity
Time O(n): fast catches slow before slow has gone once round the loop, so slow takes fewer than n steps and fast fewer than 2n. Memory O(1): two pointers and no set of visited nodes.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗