CODEWITHSUNDEEP
algorithmlinked-listcode-duplicationcontrol-flow
fredoverflow
fredoverflow

Reputation: 263280

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?

Upvotes: 3

Views: 942

Answers (4)

dogbane
dogbane

Reputation: 274788

You can use a single if-statement and use the fact that || is a short-circuit operator. This is a bit more concise, but may be harder to understand and there is still code duplication.

    do
    {
        if ((hare = hare.next()) == back || 
            (hare = hare.next()) == back) 
                return;            
        tortoise = tortoise.next();
    }
    while (tortoise != hare);

Upvotes: 1

fredoverflow
fredoverflow

Reputation: 263280

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

Upvotes: 1

Ani
Ani

Reputation: 113462

Is there a way to get rid of the code duplication inside the loop?

How about:

for(int i = 0; i < 2; i++)
{
    hare = hare.next();
    if (hare == back) return;
}

 tortoise = tortoise.next();

That isn't a massive improvement by any means.

Am I right in assuming that I don't need a check after making the tortoise take a step forward?

Yes, as you correctly reason, the tortoise is always behind the hare just before it moves; so the tortoise is always covering ground that has been covered before.

If the data-structure were for any reason mutated during the race, this would of course no longer be true (but if so, you would have much bigger problems).

Any other ways to simplify/beautify this code?

Not that I can think of.

Upvotes: 2

Jonathan
Jonathan

Reputation: 13624

To avoid the duplication, you could use a for (int i = 0; i < 2; i++) loop. Other than that, I think you've pretty much got the simplest code you can have right there.

Upvotes: 0

Related Questions