4

In the first part of Floyd's algorithm, the hare moves two steps for every step of the tortoise. If the tortoise and hare ever meet, there is a cycle, and the meeting point is part of the cycle, but not necessarily the first node in the cycle.

I cannot understand why two pointers must meet sometime if the circle exist? How about replace "two steps" with "three steps"?

I hope someone could prove it to me...

Maxmengt
  • 107
  • 1
  • 7
  • @MattTimmermans Actually no. – Maxmengt Jan 13 '17 at 16:43
  • @MattTimmermans I don't think this is a duplicate. This question asks a proof of _why_ the 2 pointers are guaranteed to meet, while the other question asks the proof of the method to find the starting point of the cycle, once the 2 pointers have met. – John Bupit Jan 13 '17 at 16:46
  • 1
    Related: http://stackoverflow.com/questions/5130246/why-increase-pointer-by-two-while-finding-loop-in-linked-list-why-not-3-4-5/5130334#5130334 – templatetypedef Jan 13 '17 at 17:38

2 Answers2

9

Note that when both tortoise and hare are in the cycle, their relative speed becomes 1, virtually hare chases standing tortoise with this speed, so hare will meet tortoise in N <= Cycle_Len steps.

You can replace "two steps" with "three steps", but you have to check whether they meet at every hare substep

MBo
  • 77,366
  • 5
  • 53
  • 86
1

To add to the second part of the question, it is not guaranteed to detect the cycles containing even number of nodes, if the hare moves at 3 steps and tortoise at 1 step. If the tortoise moved at 2 steps, however, the cycle detection would be possible.

In general, if the hare moves at H steps, and tortoise moves at T steps, you are guaranteed to detect a cycle iff H = T + 1.

Consider the hare moving relative to the tortoise.

  • Hare's speed relative to the tortoise is H - T nodes per iteration.

  • Given a cycle of length N =(H - T) * k, where k is any positive integer, the hare would skip every H - T - 1 nodes (again, relative to the tortoise), and it would be impossible to for them to meet if the tortoise was in any of those nodes.

  • The only possibility where a meeting is guaranteed is when H - T - 1 = 0.

John Bupit
  • 10,406
  • 8
  • 39
  • 75
  • That's not quite correct. When T=1, a meeting is guaranteed for any H > 1, as long as the tortoise and hare start on the same node. See my answer answer here for details: https://math.stackexchange.com/questions/913499/proof-of-floyd-cycle-chasing-tortoise-and-hare – tzs Nov 25 '17 at 23:42