Can my tortoise vs. hare race be improved?

Posted by FredOverflow on Stack Overflow See other posts from Stack Overflow or by FredOverflow
Published on 2011-03-17T15:56:48Z Indexed on 2011/03/17 16:10 UTC
Read the original article Hit count: 217

Here is my code for detecting cycles in a linked list:

do
{
    hare = hare.next();
    if (hare == back) return;

    hare = hare.next();
    if (hare == back) return;

    tortoise = tortoise.next();
}
while (tortoise != hare);
throw new AssertionError("cyclic linkage");
  1. Is there a way to get rid of the code duplication inside the loop?

  2. Am I right in assuming that I don't need a check after making the tortoise take a step forward? As I see it, the tortoise can never reach the end of the list before the hare (contrary to the fable).

  3. Any other ways to simplify/beautify this code?

© Stack Overflow or respective owner

Related posts about algorithm

Related posts about linked-list