Meet then restart from the head
Updated
After Floyd meets, set p = head and leave q at the meeting node. Walk both one next at a time. Their next meet is the cycle entrance. Do not keep the 2x speed.
What to focus on
The restart equalizes the tail length with the remaining cycle offset. If the cycle includes the head, they already sit at the entrance after the first meet or after zero extra steps.
Worked examples
entrance 1
a = [4, 1, 9] as 4→1→9→1 (back to 1), met at 9- p=4, q=9
- one step: p=1, q=1
Result: entrance 1
value-as-next
a = [1, 2, 1], met at index 2- p=0, q=2
- one step: p=1, q=1
Result: entrance index 1
full cycle
a = [4, 1, 9] as 4→1→9→4 (back to 4), met inside- p=head 4, q=meet
- walk until both at 4
Result: entrance 4, the head
Try it
Write cycleStart(a). a is the start of a list that contains a cycle. Floyd has already met. p restarts at a. q stays at the meeting node. Both move one next. Return the entrance node. Do not print. After the meet on 4→1→9→1 (back to 1), restart and stop at 1. On [1, 2, 1] as i→a[i], entrance is index 1.
The list is nonempty and contains a cycle. Floyd has already met.