Skip to interview prep
Apexed

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.

After detecting a cycle with Floyd's algorithm, how do you find where the cycle starts — Data structures & algorithms interview question — Apexed