Fast and slow on a cycle
Updated
slow = slow.next, fast = fast.next.next. If there is a cycle they meet. If fast or fast.next is null, there is no cycle. Meeting proves a loop, not yet the entrance.
What to focus on
fast laps slow inside the cycle. On a tail-plus-cycle they meet inside the cycle. On an acyclic list fast hits null.
Worked examples
meet
a = [4, 1, 9] as 4→1→9→1 (back to 1)- slow 4→1, fast 4→1→9
- slow 1→9, fast 9→1→9
- meet at 9
Result: cycle, meet at 9
value-as-next
a = [1, 2, 1], walk i → a[i] from 0- slow 0→1, fast 0→1→2
- slow 1→2, fast 2→1→2
- meet at index 2
Result: cycle 1-2
no cycle
a = [4, 1, 9] as 4→1→9→null- slow 4→1, fast 4→1→9
- fast.next is null, stop
- no meet
Result: acyclic
Try it
Write hasCycle(a). a is the start of the list. The list may or may not contain a cycle. slow moves one next. fast moves two. Return true if they meet, otherwise false. 4→1→9→1 (back to 1) meets. [1, 2, 1] as i→a[i] meets. 4→1→9→null does not.
The list is nonempty. It may or may not contain a cycle — that is the question.