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: 214
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");
Is there a way to get rid of the code duplication inside the loop?
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).
Any other ways to simplify/beautify this code?
© Stack Overflow or respective owner