12. After detecting a cycle with Floyd's algorithm, how do you find where the cycle starts?
HardLinked lists
Technical
Show model answer
When slow and fast meet inside the cycle, reset one pointer to the head and move both one step at a time. They meet again exactly at the start of the cycle.
Reason: if the distance from the head to the cycle start is a, and the meeting point is b steps into a cycle of length c, then a ≡ c − b (mod c), so both pointers arrive at the start together. Keep one pointer in place and count steps around the loop to get the cycle length.