Detectando loops em listas vinculadas usando o algoritmo de Floyd

Determinar se uma determinada lista vinculada contém um loop pode ser uma tarefa desafiadora na programação Java. Um loop ocorre quando o nó final da lista se refere a um nó anterior em vez de ter uma referência nula.

Para detectar loops com eficiência, os desenvolvedores geralmente empregam o algoritmo de localização de ciclo do Floyd, também conhecido como algoritmo de tartaruga e lebre . Este algoritmo usa duas referências, uma lenta e uma rápida, que percorrem a lista em velocidades diferentes.

Por exemplo, a referência lenta avança um nó enquanto a referência rápida avança dois nós. Se a lista vinculada contiver um loop, essas referências eventualmente se encontrarão. Por outro lado, se não houver loop, a referência lenta ou rápida (ou suas referências subsequentes) se tornará nula antes que a outra chegue ao final da lista.

Aqui está uma implementação Java do algoritmo do 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 assume complexidade de espaço O(1) e é executado em tempo O(n), tornando-o eficiente em termos de memória e razoavelmente demorado.