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

Détection efficace des boucles dans les listes chaînées

La détection de boucles dans les listes chaînées est une question d'entretien classique qui nécessite une compréhension sophistiquée des structures de données et des algorithmes. Nous présentons une solution méticuleuse à ce problème en utilisant l'algorithme de recherche de cycle de Floyd.

L'algorithme de Floyd utilise deux références, l'une avançant un pas à la fois et l'autre avançant de deux pas à la fois. Cette vitesse différentielle garantit que s'il y a une boucle dans la liste, les deux références finiront par se rencontrer.

Voici une présentation étape par étape de l'algorithme :

1. Initialisez deux références, lentes et rapides, au premier nœud de la liste.
2. Avancez lentement d'un nœud et rapide de deux nœuds à chaque étape.
3. Vérifiez si lent ou rapide devient nul. Cela indique l'absence de boucle.
4. Vérifiez si lent et rapide sont égaux. Si tel est le cas, une boucle existe.

La fonction Java suivante implémente l'algorithme de Floyd :

<code class="java">public static boolean hasLoop(Node first) {

    if (first == null) // List does not exist, no loop
        return false;

    Node slow, fast; // Create two references

    slow = fast = first; // Point both to the start of the list

    while (true) {

        slow = slow.next; // 1 hop

        if (fast.next != null)
            fast = fast.next.next; // 2 hops
        else
            return false; // Next node null -> no loop

        if (slow == null || fast == null) // If either hits null, no loop
            return false;

        if (slow == fast) // If the two ever meet, we have a loop
            return true;
    }
}</code>

Cet algorithme a une complexité spatiale constante, car il n'utilise que deux références, et une complexité temporelle raisonnable de O(n), où n est le nombre de nœuds dans la liste.

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!