Gibt es eine Möglichkeit zu überprüfen, ob eine Single-Linked-Liste Zyklen für lineare Zeit enthält, ohne die Liste zu kopieren und zu ändern?Test einzelne verkettete Liste für Zyklus
Ich dachte, wir könnten versuchen, diese Liste topologisch zu sortieren. Wenn nicht, gibt es einen kleinen Zyklus ... Aber es scheint, dass es nicht funktionieren wird.
Sie können es in konstantem Raum tun, ohne das Array zu ändern.
Die Methode ist bekannt als Floyd's cycle-finding algorithm. Es basiert auf der Idee, die Liste mit zwei Zeigern zu durchlaufen, die sich mit unterschiedlichen Geschwindigkeiten bewegen. Schließlich, wenn und nur wenn die Liste einen Zyklus enthält, werden sich die Zeiger treffen. Außerdem findet der Algorithmus den Punkt, an dem die Schleife beginnt. Überprüfen Sie den angegebenen Link für weitere Details.
Wie in dem Kommentar vorgeschlagen, können Sie schnelle und langsame Iteratorlösung verwenden.
Key Einblick:
Der Schlüssel Einblick in dem Algorithmus ist, dass für beliebige ganze Zahlen i ≥ μ und k ≥ 0, x (i) = x (i + k & lgr;), wobei λ ist die Länge der Schleife zu finden und μ ist der Index des ersten Elements des Zyklus. Insbesondere gilt: i = kλ ≥ μ, wenn und nur wenn x (i) = x (2i). Somit muss der Algorithmus nur nach wiederholten Werten dieser speziellen Form, eine zweimal so weit wie die andere, vom Beginn der Sequenz an eine Wiederholung einer Vielzahl von & lgr; von wiederholen. Sobald ν gefunden ist, zeichnet der Algorithmus die Sequenz von ihrem Anfang zurück, um den ersten Wiederholungswert xμ in der Sequenz zu finden, wobei die Tatsache verwendet wird, dass λ v teilt und daher x (μ) = x (μ + v). Schließlich, sobald der Wert von μ bekannt ist, ist es trivial , die Länge λ des kürzesten Wiederholungszyklus zu finden, indem man nach die erste Position μ + λ sucht, für die x (μ + λ) = x (μ).
Referenz-Link: Floyd's Tortoise and Hare
Verwenden klassische Lösungen mit schnellen und langsamen Iterator. Es kann Ihnen sogar sagen, wo die Schleife beginnt – teivaz
Sie könnten ein dfs tun und wenn Sie einen besuchten Knoten erreichen, dann ist es entweder eine Kreuzkante oder eine Hinterkante. Um Rückflanken zu unterscheiden, verwenden Sie "Farben", um zu bestimmen, ob Sie gerade einen Knoten bearbeiten (rekursiv für seine untergeordneten Elemente) oder die Verarbeitung abgeschlossen haben, um ihn erneut auszuführen). Dann sind alle hinteren Kanten Zyklen. –
Mögliches Duplikat von [Wie erkenne ich eine Schleife in einer verknüpften Liste?] (Http://stackoverflow.com/questions/2663115/how-to-detect-a-loop-in-a-linked-list) –