Geek asks and answers

Can I improve my turtle and hare?

Here is my code for detecting loops 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 code duplication inside a loop?

  • Do I really assume that I don’t need a check after the turtle takes a step forward? As I see it, a turtle can never reach the end of the list to a hare (contrary to fable).

  • Any other ways to simplify / decorate this code?

+3
source share
4 answers

Here is my improved code based on Steve's comment (with node feedback):

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

I do not see a place where this will violate the client code, and my unit tests confirm this. Fine:)

+1
source

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

What about:

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

 tortoise = tortoise.next();

.

, , ?

, , , ; , .

- , , , ( , ).

/ ?

, .

+2

if , || . , , .

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

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

0
source

More articles:


All Articles