algorithm - moraleja - la liebre y la tortuga resumen

¿Se puede mejorar mi raza tortuga vs. liebre?

Question

Aquí está mi código para detectar ciclos en una lista vinculada:

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. ¿Hay alguna forma de deshacerse de la duplicación del código dentro del ciclo?

2. ¿Estoy en lo cierto al suponer que no necesito un control después de hacer que la tortuga avance un paso adelante? Según lo veo, la tortuga nunca puede llegar al final de la lista antes que la liebre (al contrario de la fábula).

3. ¿Alguna otra forma de simplificar / embellecer este código?

Answer 1

¿Hay alguna forma de deshacerse de la duplicación del código dentro del ciclo?

Qué tal si:

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

 tortoise = tortoise.next();

Esa no es una mejora masiva de ninguna manera.

¿Estoy en lo cierto al suponer que no necesito un control después de hacer que la tortuga avance un paso adelante?

Sí, como razonan correctamente, la tortuga siempre está detrás de la liebre justo antes de moverse; por lo que la tortuga siempre está cubriendo el suelo que se ha cubierto antes.

Si la estructura de datos se mudara por algún motivo durante la carrera, esto ya no sería cierto (pero si fuera así, tendría problemas mucho más grandes).

¿Alguna otra forma de simplificar / embellecer este código?

No es que yo pueda pensar.

Answer 2

Aquí está mi código mejorado basado en el comentario de Steve (que tiene el enlace del nodo centinela posterior a sí mismo):

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

No veo ningún lugar donde esto rompa el código del cliente, y las pruebas de mi unidad lo confirman. Excelente :)

Answer 3

Para evitar la duplicación, puede usar un bucle for (int i = 0; i < 2; i++) . Aparte de eso, creo que ya tienes el código más simple que puedes tener ahí.

Answer 4

Puedes usar un solo enunciado if y usar el hecho de que || es un operador de cortocircuito. Esto es un poco más conciso, pero puede ser más difícil de entender y aún hay duplicación de código.

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