In tortoise and hare algorithm, Why we make the hare make 2 step forwards and check them

Question

In tortoise and hare algorithm why do we always make hare go two steps forward and hare 1 step forward and then compare them, we can also make the hare go 1 step forward and then check if its equal again then increment both the tortoise and hare again check them if they are equal! I think this will help in finding the loop faster?

For eg. this pseudocode

tortoise := firstNode
hare := firstNode

forever:

  if hare == end 
    return 'No Loop Found'

  hare := hare.next

  if hare == end
    return 'No Loop Found'
   if hare==tortoise
return true

  hare = hare.next
  tortoise = tortoise.next

  if hare == tortoise
    return 'Loop Found'

possible duplicate of [Explain how finding cycle start node in cycle linked list work?](http://stackoverflow.com/questions/2936213/explain-how-finding-cycle-start-node-in-cycle-linked-list-work) — Greg Hewgill, Jul 17 '14 at 03:37
I don't think this question is answered in the "duplicate" post. — Mark Ransom, Jul 17 '14 at 04:05
@MarkRansom: the hare and the tortoise is best explained with a scale model. Words just never seem to be good enough. I remembered trying to explain this simple and clever algorithm before -- http://stackoverflow.com/questions/16092913/how-would-i-find-an-infinite-loop-in-an-array-of-pointers/16094005#16094005 -- and not everyone was satisfied with that explanation either. But I've tried again here anyway. — rici, Jul 17 '14 at 05:28

score 7 · Accepted Answer · answered Jul 17 '14 at 05:26

The path consists of a tail and a loop; both the hare and the tortoise have to traverse the tail before they get to the loop. Since the hare moves two steps at a time, it gets to the loop first, and runs around the loop until the tortoise arrives. Up until the point at which the tortoise reaches the loop, it is not possible for the two of them to occupy the same cell.

Once the tortoise reaches the start of the loop, the hare is somewhere in the loop, effectively k steps behind the tortoise for some k, where k is certainly less than the loop size. For each step the tortoise makes, the hare makes two, which puts the hare one step closer to the tortoise. So after the tortoise moves one step, the distance between them is k-1 and then the next step it is k-2 and so on, until the hare catches up after k steps.

The hare never passes the tortoise in the loop, so there is no point checking for the hare being in the place the hare leaps over; it cannot be there. The extra check, therefore, will always fail, and including it will only slow the algorithm down.

Best explanation I've seen. Describing the hare as being *behind* the tortoise in the loop makes everything click into place! — j_random_hacker, Jul 17 '14 at 08:01
Thanks for the brilliant ans!!But @rici we do have to check for null condition after making one step forward(for hare) take one step forward and then again check for null.ryt? — user3847425, Jul 17 '14 at 13:38
@user3847425: Yes, if it is possible that the next pointer is null, you have to check at each step of the hare. (If, however, `end->next` is `end`, the check can be deferred.) — rici, Jul 17 '14 at 15:39

In tortoise and hare algorithm, Why we make the hare make 2 step forwards and check them

1 Answers1