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, 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:
Prinzip:
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>
Floyds Zyklusfindungsalgorithmus bietet die folgenden Vorteile:
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!