Angenommen, Sie haben eine verknüpfte Listenstruktur in Java. Es besteht aus Knoten:
class Node {
Node next;
// some user data
}
und jeder Knoten zeigt auf den nächsten Knoten, mit Ausnahme des letzten Knotens, der für den nächsten Null hat. Angenommen, es besteht die Möglichkeit, dass die Liste eine Schleife enthält - dh der letzte Knoten hat anstelle einer Null einen Verweis auf einen der Knoten in der Liste, die davor standen.
Was ist die beste Art zu schreiben?
boolean hasLoop(Node first)
Was würde zurückkehren, true
wenn der angegebene Knoten der erste einer Liste mit einer Schleife ist, und false
ansonsten? Wie können Sie so schreiben, dass es konstant viel Platz und eine angemessene Zeit benötigt?
Hier ist ein Bild davon, wie eine Liste mit einer Schleife aussieht:
java
algorithm
data-structures
linked-list
jjujuma
quelle
quelle
finite amount of space and a reasonable amount of time?
:)Antworten:
Sie können den Zyklusfindungsalgorithmus von Floyd verwenden , der auch als Schildkröten- und Hasenalgorithmus bezeichnet wird .
Die Idee ist, zwei Verweise auf die Liste zu haben und sie mit unterschiedlicher Geschwindigkeit zu verschieben . Bewegen Sie einen nach
1
Knoten vorwärts und den anderen nach2
Knoten.next
)null
.Java-Funktion zur Implementierung des Algorithmus:
quelle
fast.next
next
if(fast.next!=null)fast=fast.next.next;
Hier ist eine Verfeinerung der Fast / Slow-Lösung, die Listen mit ungeraden Längen korrekt verarbeitet und die Klarheit verbessert.
quelle
slow == fast.next
dannslow
wird gleichfast
bei der nächsten Iteration; Es wird höchstens eine Iteration auf Kosten eines zusätzlichen Tests für jede Iteration gespeichert.slow
kann vorher nicht null werden,fast
da es dem gleichen Referenzpfad folgt (es sei denn, Sie haben die Liste gleichzeitig geändert. In diesem Fall sind alle Wetten deaktiviert).Besser als Floyds Algorithmus
Richard Brent beschrieb einen alternativen Zykluserkennungsalgorithmus , der dem Hasen und der Schildkröte [Floyds Zyklus] ziemlich ähnlich ist, außer dass sich der langsame Knoten hier nicht bewegt, sondern später an die Position des schnellen Knotens bei fest "teleportiert" wird Intervalle.
Die Beschreibung finden Sie hier: http://www.siafoo.net/algorithm/11 Brent behauptet, sein Algorithmus sei 24 bis 36% schneller als der Floyd-Zyklusalgorithmus. O (n) Zeitkomplexität, O (1) Raumkomplexität.
quelle
slow.next != null
? Soweit ich sehen kannslow
ist immer hinter oder gleichfast
.Eine alternative Lösung zu Turtle and Rabbit, nicht ganz so schön, da ich die Liste vorübergehend ändere:
Die Idee ist, die Liste zu durchlaufen und sie im Laufe der Zeit umzukehren. Wenn Sie dann zum ersten Mal einen Knoten erreichen, der bereits besucht wurde, zeigt sein nächster Zeiger "rückwärts", wodurch die Iteration wieder in Richtung
first
fortgesetzt wird, wo sie endet.Testcode:
quelle
Schildkröte und Hase
Schauen Sie sich Pollards Rho-Algorithmus an . Es ist nicht ganz das gleiche Problem, aber vielleicht verstehen Sie die Logik daraus und wenden sie auf verknüpfte Listen an.
(Wenn Sie faul sind, können Sie einfach die Zykluserkennung überprüfen - überprüfen Sie den Teil über die Schildkröte und den Hasen.)
Dies erfordert nur eine lineare Zeit und 2 zusätzliche Zeiger.
In Java:
(Die meisten Lösungen suchen nicht nach beiden
next
undnext.next
nach Nullen. Da die Schildkröte immer im Rückstand ist, müssen Sie sie auch nicht auf Null prüfen - der Hase hat das bereits getan.)quelle
Der Benutzer unicornaddict hat oben einen netten Algorithmus, der jedoch leider einen Fehler für nicht-loopy Listen mit ungerader Länge> = 3 enthält. Das Problem ist, dass er
fast
kurz vor dem Ende der Liste "stecken bleiben" kann, ihnslow
einholt und Eine Schleife wird (fälschlicherweise) erkannt.Hier ist der korrigierte Algorithmus.
quelle
In diesem Zusammenhang gibt es überall eine Menge Textmaterialien. Ich wollte nur eine schematische Darstellung veröffentlichen, die mir wirklich geholfen hat, das Konzept zu verstehen.
Wenn sich schnell und langsam am Punkt p treffen,
Zurückgelegte Strecke schnell = a + b + c + b = a + 2b + c
Zurückgelegte Strecke langsam = a + b
Da ist das schnelle 2 mal schneller als das langsame. Also a + 2b + c = 2 (a + b) , dann erhalten wir a = c .
Wenn also wieder ein anderer langsamer Zeiger von Kopf nach q läuft, läuft gleichzeitig ein schneller Zeiger von p nach q , sodass sie sich am Punkt q zusammen treffen .
quelle
a
es größer als die Schleifenlänge ist, führt fast mehrere Schleifen aus, und die Formeldistance (fast) = a + b + b + c
ändert sich,a + (b+c) * k + b
um einen zusätzlichen Parameter einzuführenk
, der die Anzahl der von schnell eins erstellten Lopps zählt.Algorithmus
Komplexität
quelle
n
behoben seinequals
undhashCode
. Es ist nicht dasselbe. Und es störtnull
das letzte Element. Und die Frage sagte nichts über das Speichern der Knoten in einemLinkedList
.Das Folgende ist möglicherweise nicht die beste Methode - es ist O (n ^ 2). Es sollte jedoch dazu dienen, die Arbeit (irgendwann) zu erledigen.
quelle
Verzeihen Sie mir meine Unwissenheit (ich bin noch ziemlich neu in Java und Programmierung), aber warum sollte das oben genannte nicht funktionieren?
Ich denke, dies löst nicht das Problem des konstanten Platzbedarfs ... aber es kommt zumindest in angemessener Zeit dort an, richtig? Es wird nur der Platz der verknüpften Liste plus der Platz einer Menge mit n Elementen benötigt (wobei n die Anzahl der Elemente in der verknüpften Liste oder die Anzahl der Elemente ist, bis eine Schleife erreicht ist). Und für die Zeit würde eine Worst-Case-Analyse meiner Meinung nach O (nlog (n)) vorschlagen. SortedSet-Suchvorgänge für enthält () sind log (n) (überprüfen Sie das Javadoc, aber ich bin mir ziemlich sicher, dass die zugrunde liegende Struktur von TreeSet TreeMap ist, dessen wiederum ein rot-schwarzer Baum ist), und im schlimmsten Fall (keine Schleifen, oder Schleife ganz am Ende), es muss n Nachschlagen machen.
quelle
Wenn wir die Klasse einbetten dürfen
Node
, würde ich das Problem lösen, wie ich es unten implementiert habe.hasLoop()
läuft in O (n) Zeit und nimmt nur den Raum voncounter
. Scheint dies eine angemessene Lösung zu sein? Oder gibt es eine Möglichkeit, dies ohne Einbettung zu tunNode
? (Offensichtlich würde es in einer realen Implementierung mehr Methoden wieRemoveNode(Node n)
usw. geben.)quelle
Sie können dies sogar in konstanter O (1) -Zeit tun (obwohl dies nicht sehr schnell oder effizient wäre): Es gibt eine begrenzte Anzahl von Knoten, die der Arbeitsspeicher Ihres Computers aufnehmen kann, beispielsweise N Datensätze. Wenn Sie mehr als N Datensätze durchlaufen, haben Sie eine Schleife.
quelle
quelle
Verwenden Sie die obige Funktion, um eine Schleife in der verknüpften Liste in Java zu erkennen.
quelle
Das Erkennen einer Schleife in einer verknüpften Liste kann auf eine der einfachsten Arten erfolgen, was zu einer O (N) -Komplexität unter Verwendung von Hashmap oder O (NlogN) unter Verwendung eines sortierungsbasierten Ansatzes führt.
Erstellen Sie beim Durchlaufen der Liste ab Kopf eine sortierte Adressliste. Wenn Sie eine neue Adresse einfügen, überprüfen Sie, ob die Adresse bereits in der sortierten Liste vorhanden ist, was die Komplexität von O (logN) erfordert.
quelle
Ich kann mir keine Möglichkeit vorstellen, dies zeitlich oder räumlich festzuhalten. Beide werden mit der Größe der Liste zunehmen.
Ich würde eine IdentityHashMap verwenden (da es noch kein IdentityHashSet gibt) und jeden Knoten in der Karte speichern. Bevor ein Knoten gespeichert wird, würden Sie includesKey darauf aufrufen. Wenn der Knoten bereits vorhanden ist, haben Sie einen Zyklus.
ItentityHashMap verwendet == anstelle von .equals, damit Sie überprüfen, wo sich das Objekt im Speicher befindet, und nicht, ob es denselben Inhalt hat.
quelle
Ich könnte furchtbar spät und neu sein, um diesen Thread zu bearbeiten. Aber dennoch..
Warum kann die Adresse des Knotens und des "nächsten" Knotens, auf den gezeigt wird, nicht in einer Tabelle gespeichert werden?
Wenn wir so tabellieren könnten
Daher wird ein Zyklus gebildet.
quelle
Hier ist mein ausführbarer Code.
Was ich getan habe, ist, die verknüpfte Liste mithilfe von drei temporären Knoten (Raumkomplexität
O(1)
) zu verehren, die die Verknüpfungen verfolgen.Die interessante Tatsache dabei ist, den Zyklus in der verknüpften Liste zu erkennen, da Sie im weiteren Verlauf nicht erwarten, zum Startpunkt (Wurzelknoten) zurückzukehren, und einer der temporären Knoten sollte auf Null gehen, es sei denn, Sie einen Zyklus haben, der auf den Wurzelknoten zeigt.
Die zeitliche Komplexität dieses Algorithmus ist
O(n)
und die räumliche Komplexität istO(1)
.Hier ist der Klassenknoten für die verknüpfte Liste:
Hier ist der Hauptcode mit einem einfachen Testfall von drei Knoten, wobei der letzte Knoten auf den zweiten Knoten zeigt:
Hier ist ein einfacher Testfall von drei Knoten, bei denen der letzte Knoten auf den zweiten Knoten zeigt:
quelle
Dieser Code ist optimiert und liefert ein schnelleres Ergebnis als der als beste Antwort ausgewählte. Dieser Code erspart Ihnen einen sehr langen Prozess des Verfolgens des Vorwärts- und Rückwärtsknotenzeigers, der im folgenden Fall auftritt, wenn wir dem Besten folgen Antwort 'Methode. Schauen Sie sich den Trockenlauf der folgenden an und Sie werden erkennen, was ich zu sagen versuche. Dann schauen Sie sich das Problem mit der unten angegebenen Methode an und messen Sie die Nr. von Schritten unternommen, um die Antwort zu finden.
1-> 2-> 9-> 3 ^ -------- ^
Hier ist der Code:
quelle
boolean hasLoop(Node first)
die true zurückgibt, wenn der angegebene Knoten der erste einer Liste mit einer Schleife ist, andernfalls false?Hier ist meine Lösung in Java
quelle
Sie können auch Floyds Schildkrötenalgorithmus verwenden, wie in den obigen Antworten vorgeschlagen.
Dieser Algorithmus kann prüfen, ob eine einfach verknüpfte Liste einen geschlossenen Zyklus hat. Dies kann erreicht werden, indem eine Liste mit zwei Zeigern iteriert wird, die sich mit unterschiedlicher Geschwindigkeit bewegen. Auf diese Weise treffen sich die beiden Zeiger bei einem Zyklus irgendwann in der Zukunft.
Bitte schauen Sie sich meinen Blog-Beitrag in der Datenstruktur der verknüpften Listen an, in dem ich auch ein Code-Snippet mit einer Implementierung des oben genannten Algorithmus in Java-Sprache eingefügt habe.
Grüße,
Andreas (@xnorcode)
quelle
Hier ist die Lösung zur Erkennung des Zyklus.
quelle
// Verknüpfungsfunktion für verknüpfte Listen finden
quelle
Dieser Ansatz hat Platzbedarf, aber eine einfachere Implementierung:
Die Schleife kann durch Speichern von Knoten in einer Karte identifiziert werden. Und bevor Sie den Knoten setzen; Überprüfen Sie, ob der Knoten bereits vorhanden ist. Wenn der Knoten bereits in der Karte vorhanden ist, bedeutet dies, dass die verknüpfte Liste eine Schleife hat.
quelle
quelle