Ich verstehe, dass das Treffen von Tortoise und Hare die Existenz einer Schleife abschließt, aber wie bringt es die Schildkröte zum Beginn der verknüpften Liste, während der Hase am Treffpunkt bleibt, gefolgt von einem Schritt nach dem anderen, damit sie sich am Anfang des Zyklus treffen?
algorithm
linked-list
cycle
floyd-cycle-finding
Leidenschaftlicher Programmierer
quelle
quelle
Antworten:
Dies ist Floyds Algorithmus zur Zykluserkennung . Sie fragen nach der zweiten Phase des Algorithmus. Wenn Sie einen Knoten gefunden haben, der Teil eines Zyklus ist, wie findet man den Beginn des Zyklus?
Im ersten Teil von Floyds Algorithmus bewegt der Hase zwei Schritte für jeden Schritt der Schildkröte. Wenn sich Schildkröte und Hase jemals treffen, gibt es einen Zyklus, und der Treffpunkt ist Teil des Zyklus, aber nicht unbedingt der erste Knoten im Zyklus.
Wenn sich Schildkröte und Hase treffen, haben wir das kleinste i (die Anzahl der von der Schildkröte unternommenen Schritte) so gefunden, dass X i = X 2i . Es sei mu die Anzahl der Schritte, die von X 0 zum Beginn des Zyklus gelangen sollen, und Lambda die Länge des Zyklus. Dann ist i = mu + a Lambda und 2i = mu + b Lambda, wobei a und b ganze Zahlen sind, die angeben, wie oft die Schildkröte und der Hase den Zyklus durchlaufen haben. Das Subtrahieren der ersten Gleichung von der zweiten ergibt i = (ba) * Lambda, also ist i ein ganzzahliges Vielfaches von Lambda. Daher ist X i + mu = X mu . X i repräsentiert den Treffpunkt von Schildkröte und Hase. Wenn Sie die Schildkröte zurück zum Startknoten X bewegen0 , und lassen Sie die Schildkröte und den Hasen mit der gleichen Geschwindigkeit fortfahren, nach mu zusätzlichen Schritten hat die Schildkröte X mu erreicht , und der Hase hat X i + mu = X mu erreicht , so dass der zweite Treffpunkt den Beginn des bezeichnet Zyklus.
quelle
X_mu
Beginn des Zyklus (per Definition von mu). Wenn Sie dann weitere Schritte ausführen, wobei i ein Vielfaches der Zykluslänge ist, landen Sie wieder beim Zyklusstart:X_mu + i
=X_mu
. Die Addition ist jedoch kommutativ. Dies entspricht dem Ausführen von i Schritten, um vom Start zum ersten TreffpunktX_i
zu gelangen, und mu zusätzlichen Schritten, um zumX_mu
Beginn des Zyklus zurückzukehren.i
an einem bestimmten Punkt des Zyklus befindet, sollte die Gleichung lauteni = mu + k + a*lambda
und2i = mu + k + b*lambda
wok
ist die Anzahl der Schritte vom Zyklusstart bis zum Treffpunkt? Das Subtrahieren beider Gleichungen ergibt jedoch das gleiche Ergebnis.Lassen Sie mich versuchen, den unter http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare bereitgestellten Zykluserkennungsalgorithmus in meinen eigenen Worten zu erläutern .
Wie es funktioniert
Lassen Sie uns eine Schildkröte und einen Hasen (Name der Zeiger) mit einem Zyklus auf den Anfang der Liste zeigen, wie in der obigen Abbildung.
Nehmen wir an, wenn wir die Schildkröte Schritt für Schritt bewegen und 2 Schritte gleichzeitig Hase, treffen sie sich schließlich zu einem bestimmten Zeitpunkt. Lassen Sie uns zeigen, dass zuallererst diese Hypothese wahr ist.
Die Abbildung zeigt eine Liste mit einem Zyklus. Der Zyklus hat eine Länge von
n
und wir sind zunächstm
Schritte vom Zyklus entfernt. Nehmen wir auch an, der Treffpunkt ist nurk
wenige Schritte vom Beginn des Zyklus entfernt und Schildkröte und Hase treffen sich, wenn die Schildkrötei
insgesamt Schritte unternommen hat. (Hare hätte bis dahin2i
insgesamt Schritte unternommen.)Die folgenden 2 Bedingungen müssen gelten:
Der erste sagt, dass die Schildkröte
i
Schritte bewegt und in dieseni
Schritten zuerst zum Zyklus gelangt. Dann durchläuft es die Zykluszeitenp
für eine positive Zahlp
. Schließlich geht es überk
mehr Knoten, bis es auf Hasen trifft.Ähnliches gilt für Hasen. Es bewegt
2i
Schritte und in diesen2i
Schritten gelangt es zuerst zum Zyklus. Dann durchläuft es die Zykluszeitenq
für eine positive Zahlq
. Schließlich geht es überk
weitere Knoten, bis es auf Schildkröte trifft.Da Hase mit der doppelten Geschwindigkeit der Schildkröte reist und die Zeit für beide konstant ist, wenn sie den Treffpunkt erreichen.
Durch die Verwendung einer einfachen Geschwindigkeits-, Zeit- und Entfernungsbeziehung
Unter m, n, k, p, q sind die ersten beiden Eigenschaften der gegebenen Liste. Wenn wir zeigen können, dass es mindestens einen Satz von Werten für k, q, p gibt, der diese Gleichung wahr macht, zeigen wir, dass die Hypothese korrekt ist.
Ein solcher Lösungssatz lautet wie folgt:
Wir können überprüfen, ob diese Werte wie folgt funktionieren:
Für dieses Set
i
istNatürlich sollten Sie sehen, dass dies nicht unbedingt das kleinstmögliche ist. Mit anderen Worten, Schildkröte und Hase haben sich vielleicht schon oft getroffen. Da wir jedoch zeigen, dass sie sich mindestens einmal treffen, können wir sagen, dass die Hypothese richtig ist. Sie müssten sich also treffen, wenn wir einen von ihnen um einen Schritt und den anderen um zwei Schritte gleichzeitig bewegen würden.
Nun können wir zum zweiten Teil des Algorithmus übergehen, in dem der Beginn des Zyklus ermittelt wird.
Zyklusbeginn
Sobald sich Schildkröte und Hase treffen, setzen wir die Schildkröte wieder an den Anfang der Liste und halten den Hasen dort, wo sie sich getroffen haben (was k Schritte vom Zyklusbeginn entfernt ist).
Die Hypothese ist, dass, wenn wir sie mit der gleichen Geschwindigkeit bewegen lassen (1 Schritt für beide), das erste Mal, dass sie sich wieder treffen, der Zyklus beginnt.
Lassen Sie uns diese Hypothese beweisen.
Nehmen wir zunächst an, ein Orakel sagt uns, was m ist.
Wenn wir sie dann m + k Schritte bewegen lassen, müsste die Schildkröte an dem Punkt ankommen, an dem sie sich ursprünglich getroffen haben (k Schritte vom Zyklusbeginn entfernt - siehe Abbildung).
Zuvor haben wir das gezeigt
m + k = (q - 2p) n
.Da m + k Schritte ein Vielfaches der Zykluslänge n sind, würde Hase in der Zwischenzeit die Zykluszeiten (q-2p) durchlaufen und zum gleichen Punkt zurückkehren (k Schritte vom Zyklusbeginn entfernt).
Anstatt sie m + k Schritte bewegen zu lassen, würde die Schildkröte am Zyklusbeginn ankommen, wenn wir sie nur m Schritte bewegen lassen. Hase wäre k Schritte vor dem Abschluss von (q-2p) Rotationen. Da es k Schritte vor dem Zyklusbeginn begann, musste der Hase am Zyklusbeginn ankommen.
Dies erklärt, dass sie sich zum ersten Mal nach einigen Schritten zu Beginn des Zyklus treffen müssten (zum ersten Mal, weil die Schildkröte erst nach m Schritten im Zyklus ankam und nie einen Hasen sehen konnte, der sich bereits darin befand der Kreislauf).
Jetzt wissen wir, dass die Anzahl der Schritte, die wir benötigen, um sie zu bewegen, bis sie sich treffen, die Entfernung vom Anfang der Liste bis zum Beginn des Zyklus ist, m. Natürlich muss der Algorithmus nicht wissen, was m ist. Es bewegt nur Schildkröte und Hase Schritt für Schritt, bis sie sich treffen. Der Treffpunkt muss der Zyklusstart sein und die Anzahl der Schritte muss der Abstand (m) zum Zyklusbeginn sein. Angenommen, wir kennen die Länge der Liste, können wir auch die Länge des Zyklus des Subtrahierens von m von der Listenlänge berechnen.
quelle
m + k = (q - 2p) n
kann weiter vereinfacht werdenm + k = q*n
. Dies liegt daran, dass die Anzahl der Schleifen, die Schildkröten nehmen, immer Null ist, da der Hase die Schildkröte niemals überholen kann, ohne sie zu treffen. Denk darüber nach.Verweisen Sie auf dieses Bild:
Von slowPointer vor dem Treffen zurückgelegte Strecke = x + y
Mit fastPointer zurückgelegte Strecke vor dem Treffen = (x + y + z) + y = x + 2y + z
Da fastPointer mit der doppelten Geschwindigkeit von slowPointer fährt und die Zeit für beide konstant ist, wenn sie den Treffpunkt erreichen.
Durch Verwendung der einfachen Geschwindigkeits-, Zeit- und Entfernungsrelation 2 (x + y) = x + 2y + z => x + 2y + z = 2x + 2y => x = z
Wenn Sie also slowPointer an den Anfang der verknüpften Liste verschieben und slowPointer und fastPointer jeweils einen Knoten verschieben, müssen beide dieselbe Entfernung zurücklegen .
Sie erreichen den Punkt, an dem die Schleife in der verknüpften Liste beginnt.
quelle
Die einfache und unterbewertete Antwort des alten Mönchs erklärt das Finden des Zyklus, wenn der schnelle Läufer nur einen einzigen vollständigen Zyklus abschließt. In dieser Antwort erkläre ich den Fall, in dem ein schneller Läufer die Schleife mehrmals ausgeführt hat, bevor der langsame Läufer in die Schleife eintritt.
Verwenden des gleichen Bildes:
Nehmen wir an, der schnelle Läufer hat die Schleife m Mal gelaufen, bevor er sich langsam und schnell trifft. Dies bedeutet, dass:
Da schnell mit der doppelten Geschwindigkeit von langsam läuft und dass sie zur gleichen Zeit gelaufen sind, bedeutet dies, dass wir die Strecke schnell fahren, wenn wir die zurückgelegte Strecke verdoppeln. So,
Das Auflösen nach x ergibt,
Im realen Szenario würde dies bedeuten, dass x = (m - 1) vollständige Schleifenläufe + ein zusätzlicher Abstand z .
Wenn wir also einen Zeiger an den Anfang der Liste setzen und den anderen am Treffpunkt belassen, führt das Verschieben mit der gleichen Geschwindigkeit dazu, dass der In-Loop-Zeiger m - 1 Läufe der Schleife abschließt und dann den anderen trifft Zeiger direkt am Schleifenanfang.
quelle
Es ist sehr sehr einfach. Sie können in Bezug auf die relative Geschwindigkeit denken. Wenn das Kaninchen zwei Knoten bewegt und die Schildkröte einen Knoten bewegt, bewegt das Kaninchen im Vergleich zur Schildkröte einen Knoten (nehmen Sie an, dass die Schildkröte in Ruhe ist). Wenn wir also einen Knoten in der zirkular verknüpften Liste verschieben, werden wir uns an diesem Punkt sicher wieder treffen.
Nachdem der verbundene Punkt in der kreisförmigen verknüpften Liste gefunden wurde, reduziert sich das Problem nun darauf, den Schnittpunkt zweier Probleme mit verknüpften Listen zu finden.
quelle
Zum Zeitpunkt der ersten Kollision bewegte die Schildkröte m + k Schritte wie oben gezeigt. Der Hase bewegt sich doppelt so schnell wie die Schildkröte, was bedeutet, dass sich der Hase 2 (m + k) Schritte bewegt hat . Aus diesen einfachen Fakten können wir das folgende Diagramm ableiten.
An diesem Punkt bewegen wir die Schildkröte zurück zum Start und erklären, dass sich sowohl Hase als auch Schildkröte Schritt für Schritt bewegen müssen. Per Definition befindet sich die Schildkröte nach m Schritten am Anfang des Zyklus. Wo wird Hase sein?
Hase wird auch am Anfang des Zyklus sein. Dies geht aus der zweiten Grafik hervor: Als die Schildkröte zum Start zurückgebracht wurde, war der Hase k Schritte in seinem letzten Zyklus. Nach m Schritten hat der Hase einen weiteren Zyklus abgeschlossen und ist mit der Schildkröte zusammengestoßen.
quelle
Ansatz:
Es gibt zwei Hinweise:
Wenn sich die beiden Zeiger treffen, zeigt dies, dass es eine Schleife gibt. Sobald sie sich getroffen haben, zeigt einer der Knoten auf den Kopf und lässt dann jeweils einen Knoten nach dem anderen fortfahren. Sie treffen sich zu Beginn der Runde.
Begründung: Wenn zwei Personen eine Kreisbahn hinuntergehen, eine mit der doppelten Geschwindigkeit der anderen, wo treffen sie sich? Genau dort, wo sie angefangen haben.
Angenommen, der schnelle Läufer hat in einer Schrittrunde einen Vorsprung von
k
Schrittenn
. wo werden sie sich treffen Genau bein-k
Schritten. Wenn der langsame Läufer(n-k)
Schritte zurückgelegt hat, hätte der schnelle Läuferk+2(n-k)
Schritte zurückgelegt. ( dhk+2n-2k
Schritte dh2n-k
Schritte ). dh(n-k)
Schritte (Der Weg ist kreisförmig und wir sind nicht besorgt über die Anzahl der Runden, nach denen sie sich treffen; wir sind nur an der Position interessiert, an der sie sich treffen).Wie kam der schnelle Läufer überhaupt zum Vorsprung
k
? Weil der langsame Läufer so viele Schritte brauchte, um den Start der Schleife zu erreichen. Der Beginn der Schleife ist also k Schritte vom Kopfknoten entfernt.Hinweis: Der Knoten, an dem sich beide Zeiger getroffen haben, ist nur
k
wenige Schritte vom Beginn der Schleife entfernt (innerhalb der Schleife), und der Kopfknoten ist auch nurk
wenige Schritte vom Beginn der Schleife entfernt. Wenn wir also einen Zeiger haben, der mit gleichem Tempo von 1 Schritt von diesen Knoten vorrückt, treffen sie sich am Anfang der Schleife.Ich glaube es ist einfach. Bitte lassen Sie mich wissen, wenn ein Teil nicht eindeutig ist.
quelle
Okay, nehmen wir an, der Hase und die Schildkröte treffen sich an einem Punkt, der k Schritte vom Beginn des Zyklus entfernt ist. Die Anzahl der Schritte vor Beginn des Zyklus beträgt mu und die Länge des Zyklus ist L.
Also jetzt am Treffpunkt ->
Von Schildkröte zurückgelegte Strecke = mu + a * L + k - Gleichung 1
(Schritte zum Erreichen des Zyklusbeginns + Schritte zum Abdecken von 'a'-Iterationen des Zyklus + k Schritte vom Beginn des Zyklus) (wobei a eine positive Konstante ist)
Vom Hasen zurückgelegte Strecke = mu + b * L + k - Gleichung 2
(Schritte zum Erreichen des Zyklusbeginns + Schritte zum Abdecken von 'b'-Iterationen des Zyklus + k Schritte vom Beginn des Zyklus) (wobei b eine positive Konstante ist und b> = a)
Die vom Hasen zurückgelegte zusätzliche Distanz ist also = Gleichung 2 - Gleichung 1 = (ba) * L.
Bitte beachten Sie, dass dieser Abstand auch dem Abstand der Schildkröte vom Startpunkt entspricht, da sich der Hase zweimal schneller bewegt als die Schildkröte. Dies kann mit 'mu + k' gleichgesetzt werden, was auch die Entfernung des Treffpunkts vom Anfang ist, wenn wir nicht mehrere Durchläufe des Zyklus einbeziehen.
Somit ist mu + k = (ba) * L.
Meine Schritte von diesem Punkt würden also zum Beginn des Zyklus zurückführen (da bereits k Schritte vom Beginn des Zyklus unternommen wurden, um den Treffpunkt zu erreichen). Dies kann im selben Zyklus oder in einem der nachfolgenden Zyklen geschehen. Wenn wir also die Schildkröte an den Anfang der verknüpften Liste bringen, werden mu Schritte benötigt, um den Startpunkt des Zyklus zu erreichen, und der Hase würde mu Schritte unternehmen, um auch den Beginn des Zyklus zu erreichen, und somit würden sich beide am treffen Startpunkt des Zyklus.
PS Ehrlich gesagt hatte ich die gleiche Frage wie das Originalplakat im Kopf und las die erste Antwort. Sie haben ein paar Dinge geklärt, aber ich konnte das Endergebnis nicht klar erreichen und habe versucht, es auf meine eigene Art und Weise zu tun fand es leichter zu verstehen.
quelle
Bildnachweis
Anrufentfernung Die Anzahl der Verbindungen, denen ein Zeiger folgt, und die Zeit die Anzahl der Iterationen, die der Algorithmus benötigt, um den langsamen Zeiger um eine Verbindung und den schnellen Zeiger um zwei Verbindungen zu bewegen. Vor einem Zyklus der Länge C befinden sich N Knoten, die mit dem Zyklusversatz k = 0 bis C-1 gekennzeichnet sind.
Um den Beginn des Zyklus zu erreichen, benötigt langsam N Zeit und Distanz. Dies bedeutet, dass schnell N Distanz im Zyklus benötigt (N um dorthin zu gelangen, N um sich zu drehen). Zum Zeitpunkt N ist also langsam beim Zyklusversatz k = 0 und schnell beim Zyklusversatz k = N mod C.
Wenn N mod C Null ist, stimmen langsam und schnell überein und der Zyklus wird zum Zeitpunkt N und der Zyklusposition k = 0 gefunden.
Wenn N mod C nicht Null ist, muss schnell jetzt langsam aufholen, was zum Zeitpunkt N C- (N mod C) Abstand im Zyklus ist.
Da sich schnell für jede langsame 1 bewegt und die Entfernung bei jeder Iteration um 1 verringert, dauert dies genauso viel zusätzliche Zeit wie die Entfernung zwischen schnell und langsam zum Zeitpunkt N, die C- (N mod C) ist. Da sich Slow von Offset 0 bewegt, ist dies auch der Offset, an dem sie sich treffen.
Wenn also N mod C Null ist, stoppt die Phase 1 nach N Iterationen zu Beginn des Zyklus. Andernfalls stoppt Phase 1 nach N + C- (N mod C) Iterationen am Offset C- (N mod C) in den Zyklus.
Ok, also Phase 2: langsam braucht N weitere Schritte, um zum Zyklus zu gelangen. An diesem Punkt liegt schnell (jetzt 1 pro Zeitschritt) bei (C- (N mod C) + N) mod C = 0. Sie treffen sich also zu Beginn des Zyklus nach Phase 2.
Der Vollständigkeit halber berechnet Phase 3 die Zykluslänge, indem sie sich noch einmal durch den Zyklus bewegt:
quelle
Reduzieren Sie das Problem auf ein Schleifenproblem und kehren Sie dann zum ursprünglichen Problem zurück
Ich finde die folgende Erklärung intuitiver.
Nehmen Sie zwei Zeiger ( 1 = Schildkröte und 2 = Hase), die vom Kopf ausgehen ( O ), 1 hat eine Schrittlänge von 1 , 2 hat eine Schrittlänge von 2 . Denken Sie an den Moment, in dem 1 den Startknoten dieses Zyklus erreicht ( A ).
Wir möchten die folgende Frage beantworten: "Wo ist 2, wenn 1 in A ist?" .
Also
OA = a
ist eine natürliche Zahl (a >= 0
). Es kann aber folgendermaßen geschrieben werden :a = k*n + b
, wobeia, k, n, b are natural numbers
:n
= die Zykluslängek >= 0
= konstant0 <= b <= n-1
Es bedeutet das
b = a % n
.ZB: wenn
a = 20
undn = 8
=>k = 2
undb = 4
weil20 = 2*8 + 4
.Die von 1 zurückgelegte Strecke beträgt
d = OA = a = k*n + b
. Aber gleichzeitig 2 CoverD = 2*d = d + d = OA + d = OA + k*n + b
. Dies bedeutet, dass wenn 2 in A ist, es abdecken mussk*n + b
. Wie Sie sehen können,k
ist die Anzahl der Runden, aber nach diesen Runden 2 wird b von A. Bisher fanden wir , wo 2 ist , wenn 1 in A. Nennen wir diesen Punkt istB
, woAB = b
.Jetzt reduzieren wir das Problem auf einen Kreis. Die Frage ist "Wo ist der Treffpunkt?" . Wo ist das C ?
In jedem Schritt verringert 2 den Abstand von 1 mit
1
(sagen wir Meter), weil 1 mit 2 weiter von 2 entfernt ist1
, gleichzeitig aber 2 um 1 näher an 1 heranrückt2
.Der Schnittpunkt ist also, wenn der Abstand zwischen 1 und 2 Null ist. Dies bedeutet, dass 2 den
n - b
Abstand verringert . Um dies zu erreichen, 1 machenn - b
Schritte, während 2 machen2*(n - b)
Schritte.Der Schnittpunkt ist also
n - b
weit von A entfernt (im Uhrzeigersinn), da dies die Entfernung ist, die 1 zurücklegt, bis er auf 2 trifft . => der Abstand zwischen C und A istCA = b
, weilAC = AB + BC = n - b
undCA = n - AC
. Denken Sie nicht, dassAC = CA
dieAC
Entfernung keine triviale mathematische Entfernung ist, sondern die Anzahl der Schritte zwischen A und C (wobei A der Startpunkt und C der Endpunkt ist).Kehren wir nun zum ursprünglichen Schema zurück.
Wir wissen das
a = k*n + b
undCA = b
.Wir können 2 neue Zeiger 1 ' und 1' 'nehmen , wobei 1' vom Kopf ( O ) und 1 '' vom Schnittpunkt ( C ) beginnt .
Während 1' geht von O nach A , 1 ‚‘ geht von C zu A und weiter bis zum Ende
k
Runden. So ist der Schnittpunkt A .quelle
Wenn sich die Zeiger an einem Punkt P treffen, wie in der Figur gezeigt, ist der Abstand Z + Y Punkt P und X + Y ist auch Punkt P, was Z = X bedeutet. Aus diesem Grund bewegt man einen Zeiger von P und einen anderen vom Start (S) bis zu seiner Begegnung, was bedeutet, dass eine gleiche Entfernung (Z oder X) zum selben Punkt M (Entfernung Z von P und X von S) bewegt wird Beginn der Schleife. Einfach!
quelle
Bei all den obigen Analysen habe ich versucht, eine kurze Analyse und ein Beispiel zu verfassen, um die Mathematik zu erklären, die alle anderen zu erklären versuchten. Auf geht's!
Analyse:
Wenn wir zwei Zeiger haben, einen schneller als den anderen, und sie zusammen verschieben, treffen sie sich schließlich wieder, um einen Zyklus anzuzeigen, oder null, um keinen Zyklus anzuzeigen.
Um den Startpunkt des Zyklus zu finden, lassen Sie ...
m
sei der Abstand vom Kopf zum Beginn des Zyklus;d
die Anzahl der Knoten im Zyklus sein;p1
sei die Geschwindigkeit des langsameren Zeigers;p2
sei die Geschwindigkeit des schnelleren Zeigers, z. 2 bedeutet Schritte durch zwei Knoten gleichzeitig.Beachten Sie die folgenden Iterationen:
Anhand der obigen Beispieldaten können wir leicht erkennen, dass die schnelleren und langsameren Zeiger, wenn sie sich treffen, nur wenige
m
Schritte vom Beginn des Zyklus entfernt sind. Um dies zu lösen, setzen Sie den schnelleren Zeiger wieder auf den Kopf und stellen Sie seine Geschwindigkeit auf die Geschwindigkeit des langsameren Zeigers ein. Wenn sie sich wieder treffen, ist der Knoten der Beginn des Zyklus.quelle
sagen wir,
Wir haben 2 Zeiger A und B, A läuft mit 1x Geschwindigkeit, B mit 2x Geschwindigkeit, beide beginnen am Anfang.
Wenn A N [0] erreicht, sollte B bereits in N [m] sein. (Hinweis: A verwendet m Schritte, um N [0] zu erreichen, und B sollte m Schritte weiter sein.)
Dann führt A k weitere Schritte aus, um mit B zu kollidieren, dh A ist bei N [k], B ist bei N [m + 2k] (Hinweis: B sollte für 2k Schritte ab N [m] ausgeführt werden)
Eine Kollision B bei N [k] bzw. N [m + 2k] bedeutet k = m + 2k, also k = -m
Um von N [k] zu N [0] zurückzukehren, benötigen wir m weitere Schritte.
Einfach gesagt, wir müssen nur m weitere Schritte ausführen, nachdem wir den Kollisionsknoten gefunden haben. Wir können einen Zeiger haben, der von Anfang an ausgeführt wird, und einen Zeiger, der vom Kollisionsknoten ausgeht. Sie treffen sich nach m Schritten bei N [0].
Daher lautet der Pseudocode wie folgt:
quelle
Ich denke nicht, dass es der Ausgangspunkt ist, wenn sie sich treffen. Aber ja, wenn sich der andere Zeiger (F) zuvor am Treffpunkt befand, befindet sich dieser Zeiger am Ende der Schleife anstelle des Starts der Schleife und des Zeigers (S), der am Anfang der Liste begonnen hat am Anfang der Schleife enden. für zB:
quelle
Eine einfache Erklärung unter Verwendung der Idee der Relativgeschwindigkeit, die in der High School gelehrt wird - Vorlesungen Physik 101 / Kinematik.
Nehmen wir an, der Abstand vom Beginn der verknüpften Liste zum Beginn des Kreises beträgt
x
Hopfen. Nennen wir den Kreisanfang als PunktX
(in Großbuchstaben - siehe Abbildung oben). Nehmen wir auch an, dass die Gesamtgröße des Kreises N Hopfen beträgt.Geschwindigkeit des Hasen = 2 * Geschwindigkeit der Schildkröte. Das ist also,
1 hops/sec
und2 hops/sec
jeweilsWenn die Schildkröte den Anfang des Kreises erreicht
X
, muss der Hasex
an der StelleY
in der Figur weiter hüpfen . (Weil Hase doppelt so weit gereist ist wie die Schildkröte).Somit Länge des verbleibenden Bogen im Uhrzeigersinn von X zu Y wäre
N-x
. Dies ist auch die relative Entfernung, die zwischen dem Hasen und der Schildkröte zurückgelegt werden muss, damit sie sich treffen können . Nehmen wir an, diese relative Distanz wird in der Zeit zurückgelegt,t_m
dh in der Zeit, um sich zu treffen. Relative Geschwindigkeit ist(2 hops/sec - 1 hops/sec)
dh1 hops/sec
. Wenn wir also relative Entfernung = relative Geschwindigkeit X Zeit verwenden, erhalten wirt
=N-x
Sek. Es wird also dauernN-x
, bis der Treffpunkt sowohl für die Schildkröte als auch für den Hasen erreicht ist.Jetzt in
N-x
Sekundenschnelle und mit1 hops/sec
Geschwindigkeit wird die Schildkröte, die früher am Punkt warX
, Nx-Hopfen abdecken, um den Treffpunkt zu erreichenM
. Das bedeutet also den TreffpunktM
an istN-x
Hopfen entgegen den Uhrzeigersinn vonX
= (was weiter impliziert) => , dass esx
Abstand von Punkt verbleibendenM
zu demX
Uhrzeigersinn.Ist
x
aber auch die Entfernung zum PunktX
vom Anfang der verknüpften Liste.Nun ist es uns egal, wie viele Hopfen
x
entsprechen. Wenn wir eine Schildkröte am Anfang der LinkedList und eine Schildkröte am Treffpunkt platzierenM
und sie hüpfen / laufen lassen, treffen sie sich am PunktX
, dem Punkt (oder Knoten), den wir benötigen.quelle
Das Arbeiten mit einem Diagramm würde helfen. Ich versuche das Problem ohne Gleichungen zu erklären.
quelle
-Es gibt k Schritte vor der Schleife. Wir wissen nicht, was k ist und müssen es nicht herausfinden. Wir können abstrakt mit nur k arbeiten.
--Nach k Schritten
----- T ist am Zyklusbeginn
----- H ist k Schritte in den Zyklus (er ging insgesamt 2k und damit k in die Schleife)
** Sie sind jetzt Loopsize - k voneinander entfernt
(Beachten Sie, dass k == K == mod (Schleifengröße, k) --eg Wenn ein Knoten 2 Schritte in einen 5-Knoten-Zyklus ist, sind es auch 7, 12 oder 392 Schritte, also wie groß der Zyklus ist, k k nicht Faktor in.
Da sie sich mit einer Geschwindigkeit von 1 Schritt pro Zeiteinheit einholen, weil sich einer doppelt so schnell bewegt wie der andere, treffen sie sich in Schleifengröße - k.
Dies bedeutet, dass k Knoten benötigt werden, um den Beginn des Zyklus zu erreichen, und daher der Abstand vom Kopf zum Zyklusstart und die Kollision zum Zyklusstart gleich sind.
Bewegen Sie nun nach der ersten Kollision T zurück zum Kopf. T und H treffen sich beim Zyklestart, wenn Sie sich mit einer Geschwindigkeit von jeweils 1 bewegen. (in k Schritten für beide)
Dies bedeutet, dass der Algorithmus ist:
// Kümmere dich um den Fall, dass k = 0 ist oder T und H sich am Kopf der Schleife treffen, indem du die Länge der Schleife berechnest
- Zählen Sie die Länge des Zyklus, indem Sie T oder H mit einem Zähler um ihn herum bewegen
- Bewegen Sie einen Zeiger T2 auf den Kopf der Liste
- Zeigerlänge der Zyklusschritte verschieben
- Bewegen Sie einen weiteren Zeiger H2 auf den Kopf
- Bewegen Sie T2 und H2 zusammen, bis sie sich zu Beginn des Zyklus treffen
das ist es!
quelle
Es gibt bereits viele Antworten darauf, aber ich habe mir einmal ein Diagramm dafür ausgedacht, das für mich visuell intuitiver ist. Vielleicht kann es anderen Menschen helfen.
Die wichtigsten Aha-Momente für mich waren:
Teilen Sie T (Schildkröte) in T1 (Pre-Loop) und T2 (In-Loop).
Subtrahieren Sie T von H , wo sie sich visuell überlappen. Was bleibt , ( H - T = H‘ ) gleich T .
quelle
Ich weiß, dass es bereits eine akzeptierte Antwort auf dieses Problem gibt, aber ich werde trotzdem versuchen, auf flüssige Weise zu antworten. Annehmen :
Nun, lassen Sie den Hasen und die Schildkröte nach der Zeit 't' von Anfang an treffen.
Beobachtungen:
Wenn, von der Schildkröte zurückgelegte Strecke = v * t = x + (bk) (sagen wir)
Dann ist die vom Hasen zurückgelegte Strecke = 2 * v * t = x + (b - k) + b (da der Hase den geschlungenen Teil bereits einmal durchlaufen hat)
Jetzt sind die Besprechungszeiten gleich.
=> x + 2 * b - k = 2 * (x + b - k)
=> x = k
Dies bedeutet natürlich, dass die Länge des Pfades, der nicht geloopt ist, der Entfernung des Startpunkts der Schleife von dem Punkt entspricht, an dem sich beide treffen.
quelle
Es ist tatsächlich leicht zu beweisen, dass sich beide am Startpunkt treffen werden, wenn man die Mathematik hinter dem Treffpunkt berücksichtigt.
Zunächst sei m der Startpunkt des Zyklus in der verknüpften Liste und n die Länge des Zyklus. Damit sich der Hase und die Schildkröte treffen können, haben wir:
Mathematischer ausgedrückt:
so treffen sie sich zum Zeitpunkt t, der ein Vielfaches der Zykluslänge sein sollte. Dies bedeutet, dass sie sich an einem Ort treffen, nämlich
(t-m) modulo n = (0-m) modulo n = (-m) modulo n
.Kommen wir nun zu der Frage zurück: Wenn Sie einen Zeiger vom Anfang der verknüpften Liste und einen anderen vom Schnittpunkt bewegen, wird der Hase (der sich innerhalb des Zyklus bewegt) nach m Schritten zu einem Punkt kommen, der ist
((-m) + m) modulo n = 0 modulo n
Das ist nichts anderes als der Startpunkt des Zyklus. Wir können also sehen, dass es nach m Schritten zum Beginn des Zyklus kommt und die Schildkröte ihn dort trifft, wenn sie m durchquert Schritte vom Beginn der verknüpften Liste .Als Randnotiz können wir die Zeit ihres Schnittpunkts auch folgendermaßen berechnen: Die Bedingung
t = 0 modulo n
besagt, dass sie sich zu einem Zeitpunkt treffen werden, der ein Vielfaches der Zykluslänge ist, und dass t auch größer als m sein sollte, als sie sich treffen würden der Kreislauf . Die benötigte Zeit ist also gleich dem ersten Vielfachen von n, das größer als m ist .quelle
Angenommen, Ihre Zeiger treffen sich am Schnittpunkt von Punkt y und z.
n und m sind die Anzahl der Schleifen, die der Zeiger vor dem Treffen schneller und langsamer nimmt.
Beziehen Sie sich für den Rest des Beweises auf das Bild. Suchen Sie den Startpunkt der Schleife in der verknüpften Liste
quelle