Comment l'algorithme de Floyd détecte-t-il les boucles dans les listes liées ?

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. En revanche, s'il n'y a pas de boucle, soit la référence lente ou rapide (ou leurs références ultérieures) deviendront nulles avant que l'autre n'atteigne la fin de la liste.

Voici une implémentation Java de l'algorithme de Floyd :

<code class="java">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.
        }
    }
}</code>

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!