Détection de boucles dans les listes chaînées à l'aide de l'algorithme de Floyd

Déterminer si une liste chaînée donnée contient une boucle peut être une tâche difficile en programmation Java. Une boucle se produit lorsque le dernier nœud de la liste fait référence à un nœud précédent au lieu d'avoir une référence nulle.

Pour détecter efficacement les boucles, les développeurs utilisent souvent l'algorithme de recherche de cycle de Floyd, également connu sous le nom d'algorithme de la tortue et du lièvre. . Cet algorithme utilise deux références, une lente et une rapide, qui parcourent la liste à des vitesses différentes.

Par exemple, la référence lente avance d'un nœud tandis que la référence rapide avance de deux nœuds. Si la liste chaînée contient une boucle, ces références finiront par se rencontrer. D'un autre côté, s'il n'y a pas de boucle, la référence lente ou rapide (ou leurs références ultérieures) deviendra nulle avant que l'autre n'atteigne la fin de la liste.

Voici une implémentation Java de l'algorithme 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.
        }
    }
}

Cet algorithme prend une complexité spatiale O(1) et s'exécute en un temps O(n), ce qui le rend à la fois efficace en mémoire et raisonnablement long.