Wie können wir den Startknoten einer Schleife in der Linkliste finden?
Nach dem Floyd'schen Zyklusfindungsalgorithmus erklärt der Punkt, an dem sich Schildkröte und Hase treffen, die zirkuläre Natur in der Linkliste.
Um den Startknoten im Zyklus zu finden, initialisieren wir den Schildkrötenzeiger zum Kopf der Liste und beginnen, den Hasen- und Schildkrötenzeiger um eine Einheit zu erhöhen. Der Punkt, an dem sie sich treffen, bezeichnet den Startknoten des Zyklus.
Bitte sagen Sie mir, wie es für die gegebene Situation funktioniert.
Die Linkliste fließt wie folgt:
%Vor%4 Antworten
Mal sehen.
Sie positionieren den Hasen und die Schildkröte bei 1, und lassen Sie sie laufen, der Hase zweimal so schnell wie die Schildkröte.
Im nullten Schritt sind beide auf 1. Im ersten Schritt bewegt sich die Schildkröte auf 2 und der Hase auf 3 und so weiter.
%Vor%So treffen sich Hase und Schildkröte um sieben.
Platziere die Schildkröte jetzt am Anfang und lass sie wieder laufen, jetzt mit der gleichen Geschwindigkeit.
%Vor%So haben sie sich tatsächlich beim ersten Element des Zyklus getroffen.
Und so funktioniert es für die gegebene Situation .
OK, lass es uns einfach halten.
Nehmen wir an, Sie haben zwei Läufer A und B. A wird um jeweils einen Knoten vorwärts bewegt, B um zwei Knoten.
Wenn es eine zyklische Liste ist, werden sie sich endlich treffen.
Zu dieser Zeit
Sagen Sie, der Abstand, um den A sich bewegt hat, ist m , also für B ist 2m
Beachten Sie auch, dass
%Vor% Weil für B, hat es sich bewegt, egal welche Entfernung A sich bewegt hat, plus k (irgendeine Anzahl, die uns egal ist) von Schleifen. a ist der Abstand vor dem Schleifenpunkt, b ist der Abstand A, der nach dem Schleifenpunkt verschoben wurde.
Dann haben wir (nach etwas Mathe)
%Vor%Jetzt setzen wir B wieder an den Anfang der Liste und reduzieren seine Geschwindigkeit auf 1.
Für B sind die a -Knoten vom Schleifenpunkt entfernt. Für A hat er den Loop-Punkt bereits um b übergeben, und nach der obigen Gleichung ist er auch a Knoten vom Loop-Punkt entfernt.
Also, nach a mehr Schritten, treffen sich A und B am Schleifenpunkt wieder.
Okay, direkte Antwort: Die [EDIT: verknüpfte Liste, nicht Sequenz], die Sie angegeben haben, enthält keine Zyklen. Folgendes wird passieren. Im ersten Teil des Algorithmus beginnen Schildkröte und Haar bei x1 = 2 bzw. x2 = 3. Dann werden sie zu x2 = 3 und x4 = 5 weitergehen. Dann zu x3 = 4 und x6 = 7. Dann zu x4 = 5 und x8 = 3. Dann wird der Hase aufhören weiterzugehen, da es nichts gibt außer x8, und der Algorithmus wird ergeben, dass keine Zyklen gefunden wurden.
Unten habe ich ein kleines GIF kompiliert, das zeigt, dass Floyds Zyklusfindung auf eine andere Sequenz angewendet wird, die Zyklen enthält.
Betrachten Sie zwei Zeiger: fast pointer (bewegt zwei Knoten gleichzeitig) und slow pointer (bewegt jeweils einen Knoten). Beide beginnen sich vom Kopf der verknüpften Liste zu bewegen.
Nach einiger Zeit tritt die slow pointer in die Schleife ein, wenn k -Knoten von head durchlaufen werden. Zu diesem Zeitpunkt hätte fast pointer den Knoten
fast pointer auf den k Knoten von slow pointer zeigt.
Jetzt bewegen sie sich weiter, bis sie sich irgendwo in der Schleife treffen. Wenn sie sich treffen, sind sie weit vom Anfang der Schleife entfernt, und zwar um genau die gleiche Anzahl von Knoten wie fast pointer von slow pointer in der Startschleife (dh die Entfernung des Startknotens der Schleife von dem Knoten wo fast pointer und slow pointer meet sind k Elemente (oder Knoten).
Und k ist auch die Entfernung des Startknotens der Schleife vom Kopf der verknüpften Liste.
Also fangen wir an, einen Zeiger vom Kopf und einen Zeiger vom Treffpunkt von fast pointer und slow pointer zu bewegen. Da der Abstand des Startknotens der Schleife k von diesen beiden Punkten ist, treffen sie sich in ihrem k Schritt am Anfangsknoten der Schleife
Tags und Links algorithm floyd-cycle-finding