Wie erkennt Floyds Cycle-Finding-Algorithmus Schleifen in verknüpften Listen?

Effiziente Schleifenerkennung in verknüpften Listen

Das Erkennen von Schleifen in verknüpften Listen ist eine klassische Interviewfrage, die ein ausgefeiltes Verständnis von Datenstrukturen und Algorithmen erfordert. Wir präsentieren eine sorgfältige Lösung für dieses Problem mithilfe des Floyd-Zyklusfindungsalgorithmus.

Floyds Algorithmus verwendet zwei Referenzen, von denen eine jeweils um einen Schritt und die andere jeweils um zwei Schritte voranschreitet. Diese unterschiedliche Geschwindigkeit stellt sicher, dass die beiden Referenzen irgendwann zusammentreffen, wenn es eine Schleife in der Liste gibt.

Hier ist eine schrittweise Aufschlüsselung des Algorithmus:

1. Initialisieren Sie zwei Verweise, langsam und schnell, auf den ersten Knoten in der Liste.
2. Langsam um einen Knoten und schnell um zwei Knoten bei jedem Schritt vorrücken.
3. Überprüfen Sie, ob entweder langsam oder schnell null wird. Dies zeigt das Fehlen einer Schleife an.
4. Überprüfen Sie, ob langsam und schnell gleich sind. Wenn dies der Fall ist, existiert eine Schleife.

Die folgende Java-Funktion implementiert Floyds Algorithmus:

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

Dieser Algorithmus hat eine konstante Raumkomplexität, da er nur zwei Referenzen verwendet, und eine angemessene zeitliche Komplexität von O(n), wobei n die Anzahl der Knoten in der Liste ist.

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