patternCritical
Floyd's Cycle detection algorithm | Determining the starting point of cycle
Viewed 0 times
floydcycledeterminingthestartingpointalgorithmdetection
Problem
I am seeking help understanding Floyd's cycle detection algorithm. I have gone through the explanation on wikipedia (http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare)
I can see how the algorithm detects cycle in O(n) time. However, I am unable to visualise the fact that once the tortoise and hare pointers meet for the first time, the start of the cycle can be determined by moving tortoise pointer back to start and then moving both tortoise and hare one step at a time. The point where they first meet is the start of the cycle.
Can someone help by providing an explanation, hopefully different from the one on wikipedia, as I am unable to understand/visualise it?
I can see how the algorithm detects cycle in O(n) time. However, I am unable to visualise the fact that once the tortoise and hare pointers meet for the first time, the start of the cycle can be determined by moving tortoise pointer back to start and then moving both tortoise and hare one step at a time. The point where they first meet is the start of the cycle.
Can someone help by providing an explanation, hopefully different from the one on wikipedia, as I am unable to understand/visualise it?
Solution
You can refer to "Detecting start of a loop in singly linked list", here's an excerpt:
Distance travelled by
Distance travelled by
Since
\begin{align*}
2*\operatorname{dist}(\text{slowPointer}) &= \operatorname{dist}(\text{fastPointer})\\
2(x+y) &= x+2y+z\\
2x+2y &= x+2y+z\\
x &= z
\end{align*}
Hence by moving
They will reach at the point where the loop starts in the linked list.
Distance travelled by
slowPointer before meeting $= x+y$Distance travelled by
fastPointer before meeting $=(x + y + z) + y = x + 2y + z$Since
fastPointer travels with double the speed of slowPointer, and time is constant for both when both pointers reach the meeting point. So by using simple speed, time and distance relation (slowPointer traveled half the distance):\begin{align*}
2*\operatorname{dist}(\text{slowPointer}) &= \operatorname{dist}(\text{fastPointer})\\
2(x+y) &= x+2y+z\\
2x+2y &= x+2y+z\\
x &= z
\end{align*}
Hence by moving
slowPointer to start of linked list, and making both slowPointer and fastPointer to move one node at a time, they both have same distance to cover.They will reach at the point where the loop starts in the linked list.
Context
StackExchange Computer Science Q#10360, answer score: 95
Revisions (0)
No revisions yet.