Search code examples
algorithmlinked-listcode-duplicationcontrol-flow

Can my tortoise vs. hare race be improved?


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?


Solution

  • Here is my improved code based on Steve's comment (having the back sentinel node link to itself):

    while (hare != back)
    {
        tortoise = tortoise.next();
        hare = hare.next().next();
        if (hare == tortoise) throw new AssertionError("cyclic linkage");
    }
    

    I don't see any place where this would break client code, and my unit tests confirm that. Great :)