Wie erkennt Floyds Algorithmus Schleifen in verknüpften Listen?

Schleifen in verknüpften Listen mithilfe des Floyd-Algorithmus erkennen

Bestimmen, ob eine bestimmte verknüpfte Liste eine Schleife enthält, kann in der Java-Programmierung eine herausfordernde Aufgabe sein. Eine Schleife tritt auf, wenn der letzte Knoten in der Liste auf einen vorherigen Knoten verweist, anstatt eine Nullreferenz zu haben.

Um Schleifen effizient zu erkennen, verwenden Entwickler häufig Floyds Zyklusfindungsalgorithmus, auch bekannt als Tortoise-and-Hare-Algorithmus . Dieser Algorithmus verwendet zwei Referenzen, eine langsame und eine schnelle, die die Liste mit unterschiedlichen Geschwindigkeiten durchlaufen.

Zum Beispiel rückt die langsame Referenz um einen Knoten vor, während die schnelle Referenz um zwei Knoten vorrückt. Wenn die verknüpfte Liste eine Schleife enthält, treffen diese Referenzen schließlich aufeinander. Wenn es andererseits keine Schleife gibt, werden entweder die langsame oder die schnelle Referenz (oder ihre nachfolgenden Referenzen) null, bevor die andere das Ende der Liste erreicht.

Hier ist eine Java-Implementierung von Floyds Algorithmus :

<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>

Dieser Algorithmus benötigt eine O(1)-Raumkomplexität und läuft in O(n)-Zeit, wodurch er sowohl speichereffizient als auch einigermaßen zeitaufwändig ist.

Das obige ist der detaillierte Inhalt vonWie erkennt Floyds Algorithmus Schleifen in verknüpften Listen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!