2

I understand the concept of Floyd's algorithm for cycle detection. It concludes that if the Tortoise travels twice as fast as the Hare, and if the Tortoise has a head start of k meters in a loop, the Tortoise and the Hare will meet k meters before the loop.

In the case of singly linkedlist, you have pointer A travelling twice as fast as pointer B. This means that if it takes pointer B k-steps to reach the entry point of the loop(which we dont know where it is yet), pointer A will already have a head start of k nodes inside the loop. Therefore, two pointers will meet k nodes before the entry point of the loop. Thus, if we move pointer B back to the head pointer and keep pointer A at the meeting point(now both pointers are k nodes away from the entry point), and move both at the same pace, they will meet at the entry point of the loop.

How can you prove that the algorithm will work in the following boundary cases?

  1. A linkedlist where the last node loop back to the head. In this case, what will the head start value, k, be?
  2. A super long linkedlist, 1000 nodes, and has a small loop at the end, 3 nodes. Pointer A will have a head start of 1000, which means by the time pointer B reaches the entry point of the loop, A will already have looped many times.
  3. What if there is a loop of 1 node?

This is not homework. I was told by an interviewer that this algorithm won't work if I have a small loop. He didn't explain why.

mirage1s7
  • 277
  • 1
  • 5
  • 10

3 Answers3

5

It is clear that both pointers will eventually reach the loop if there is one. Lets assume, the loop has length N. We can do calculations of the position in the loop modulo N.

Now say pointer A is at position a and pointer B is at position b. After s steps, A will be at a+2s mod N and B will be at b+s mod N. For the two pointers to meet we must have

a+2s = b+s (mod N)
a+s = b (mod N)
s = b - a (mod N)

So after b - a (mod N) steps the two pointers will meet.

Henry
  • 42,982
  • 7
  • 68
  • 84
  • (mod N) means, all calculations are done in the ring of congruence classes mod N. "mod" is not an operator. – Henry Nov 12 '13 at 21:05
3

Just consider this: after n moves you can be sure that both pointers will be in the cycle or some of them has the end. With next n moves you can be sure that A and B will meet and some point since the cycle's size is <= n and since with every step the difference between them reduces with 1.

sve
  • 4,336
  • 1
  • 19
  • 30
2

Of course it works with a small loop. Consider a loop of two nodes. That is:

A => B => C => B

So the tortoise and hare start at A. The table below shows what happens:

Tortoise  Hare
   A       A
   C       B
   C       C

When there are only two nodes, then the tortoise always ends where it started. So the tortoise will essentially remain still while the hare moves one node each time and eventually catch up.

The same thing happens, by the way, when you have a loop of only one node. That is, when a node loops back on itself.

Henry's answer gives the mathematical proof.

Jim Mischel
  • 131,090
  • 20
  • 188
  • 351