Erkennt Floyds Cycle-Finding-Algorithmus effizient Schleifen in verknüpften Listen?

Erkennen von Schleifen in verknüpften Listen mit Floyds Cycle-Finding-Algorithmus

Verknüpfte Listen, eine grundlegende Datenstruktur in der Informatik, werden häufig zur Darstellung einer Folge von Elementen verwendet. In bestimmten Szenarien kann eine verknüpfte Liste eine Schleife enthalten, bei der der letzte Knoten auf einen vorherigen Knoten verweist und so eine kreisförmige Struktur entsteht. Das Erkennen des Vorhandenseins solcher Schleifen ist eine entscheidende Aufgabe für verschiedene Operationen mit verknüpften Listen.

Floyds Zyklusfindungsalgorithmus

Floyds Zyklusfindungsalgorithmus, auch bekannt als Schildkröten- und Hasenalgorithmus, liefert eine effiziente Möglichkeit, Schleifen in verknüpften Listen zu erkennen. Der Algorithmus basiert auf dem Prinzip, zwei Zeiger (Referenzen) mit unterschiedlicher Geschwindigkeit durch die Liste zu bewegen:

1. Schildkröte (langsamer Zeiger): Bewegt sich jeweils um einen Knoten vorwärts.
2. Hase (Schnellzeiger):Bewegt sich jeweils um zwei Knoten vorwärts.

Prinzip:

• Schleife vorhanden:Wenn es eine Schleife in der Liste gibt, treffen sich Schildkröte und Hase schließlich am selben Knoten, was auf das Vorhandensein einer Schleife hinweist.
• Keine Schleife :Wenn die Liste keine Schleife enthält, erreicht entweder die Schildkröte oder der Hase das Ende der Liste (einen Nullzeiger), was das Fehlen einer Schleife signalisiert.

Java-Implementierung

Die folgende Java-Funktion implementiert Floyds Zyklusfindungsalgorithmus:

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

    if(first == null) // list does not exist..so no loop either
        return false;

    Node slow, fast; // create two references.

    slow = fast = first; // make both refer 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 must have a loop
            return true;
    }
}</code>

Vorteile

Floyds Zyklusfindungsalgorithmus bietet die folgenden Vorteile:

• Konstante Raumkomplexität: Es sind nur zwei Zeiger (Referenzen) erforderlich, wodurch seine Raumkomplexität konstant (O(1)) wird.
• Lineare Zeitkomplexität: Die Die Zeitkomplexität des Algorithmus beträgt O(n), wobei n die Anzahl der Knoten in der verknüpften Liste ist.

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