Graph Theory37 sections · 1633 units
Open in Course

Finding Cycle Start

(The meeting point trick)

After slow and fast meet, reset slow to the starting node. Keep fast at the meeting point. This setup uses the geometric relationship between tail and cycle. Now move both one step at a time. When they meet again, that is the start of the cycle.

Both pointers move at the same speed now. This works because of the distance relationship between the tail length and meeting point. The math guarantees they meet at cycle start after exactly μ\mu steps, where μ\mu is the tail length.