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?

  • 2
    I found the answer on stackoverflow. Thanks if anyone was looking into this for me. And for those who like me wanted an explanation, please refer to: stackoverflow.com/questions/3952805/… The chosen answer to the question, explains it! – Anurag Kapur Mar 7 '13 at 12:39
  • Hi @Anurag. Just for your information, I've done a blog post on the "Tortoise and the Hare" algorithm here – Kyle Oct 19 '13 at 19:25
  • Do you know why the fast variable, or the "hare" needs to move at twice the speed as tortoise, rather than just one ahead? – devdropper87 Oct 2 '15 at 16:09
  • Nicely explained with program: javabypatel.blogspot.in/2015/12/detect-loop-in-linked-list.html – Jayesh Dec 10 '15 at 12:03

You can refer to "Detecting start of a loop in singly linked list", here's an excerpt:

enter image description here

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 the 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.

  • 1
    This is a magnificient, simple and intiuitive explanation - and the proof is both elegant and obvious. This should be the accepted answer. – quantum Dec 20 '16 at 21:38
  • Here you have made an assumption that they will meet after one rotation. There can be cases (where cycle is small) where they might meet after certain no. of rotations. – Jot Waraich Jul 19 at 9:34

I have seen the accepted answer as proof elsewhere too. However, while its easy to grok, it is incorrect. What it proves is

$x = z$ (which is obviously wrong, and the diagram just makes it seem plausible due to the way it is sketched).

What you really want to prove is (using the same variables as described in the diagram in the accepted answer above):

$z = x\ mod\ (y + z)$

$(y + z)$ is the loop length, $L$

so, what we want to prove is:

$z = x\ mod\ L$

Or that z is congruent to x (modulo L)

Following proof makes more sense to me:

Meeting point, $M = x + y$

$2(x + y) = M + kL$, where $k$ is some constant. Basically, distance travelled by the fast pointer is $x + y$ plus some multiple of loop length, $L$

$x + y = kL$

$x = kL - y$

The above equation proves that $x$ is the same as some multiple of loop length, $L$ minus $y$. So, if the fast pointer starts at the meeting point, $M$ or at $x + y$, then it will end up at the start of the loop.

up vote 0 down vote accepted

I found the answer on stackoverflow. Thanks if anyone was looking into this for me. And for those who like me wanted an explanation, please refer to: https://stackoverflow.com/questions/3952805/proof-of-detecting-the-start-of-cycle-in-linked-list The chosen answer to the question, explains it!

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.