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?
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 :)