Detección de bucles en listas enlazadas utilizando el algoritmo de Floyd

Determinar si una lista enlazada determinada contiene un bucle puede ser una tarea desafiante en la programación Java. Se produce un bucle cuando el nodo final de la lista hace referencia a un nodo anterior en lugar de tener una referencia nula.

Para detectar bucles de manera eficiente, los desarrolladores suelen emplear el algoritmo de búsqueda de ciclos de Floyd, también conocido como algoritmo de la liebre y la tortuga. . Este algoritmo utiliza dos referencias, una lenta y otra rápida, que atraviesan la lista a diferentes velocidades.

Por ejemplo, la referencia lenta avanza en un nodo mientras que la referencia rápida avanza en dos nodos. Si la lista vinculada contiene un bucle, estas referencias eventualmente se encontrarán. Por otro lado, si no hay ningún bucle, la referencia lenta o rápida (o sus referencias posteriores) se volverá nula antes de que la otra llegue al final de la lista.

Aquí hay una implementación Java del algoritmo de Floyd. :

boolean hasLoop(Node first) {
    if (first == null) {
        return false; // List does not exist, so no loop
    }

    Node slow, fast; // Create two references.
    slow = fast = first; // Make both refer to the start of the list.

    while (true) {
        slow = slow.next; // One hop.

        if (fast.next != null) {
            fast = fast.next.next; // Two hops.
        } else {
            return false; // No loop.
        }

        if (slow == null || fast == null) {
            return false; // No loop.
        }

        if (slow == fast) {
            return true; // Loop detected.
        }
    }
}

Este algoritmo requiere una complejidad de espacio O(1) y se ejecuta en un tiempo O(n), lo que lo hace eficiente en memoria y requiere mucho tiempo.