Erläutern, wie der Suchzyklus-Startknoten in der Zyklus-verknüpften Liste funktioniert?

Lassen Sie mich versuchen zu klären, die Zyklus-Erkennung-Algorithmus, ist im http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare in meinen eigenen Worten.

Verweise ich auf die Abbildung in meiner Erklärung.

Wie es funktioniert

Wir haben eine Schildkröte und ein Hase (name der Zeiger) zeigt auf den Anfang der Liste mit einem Zyklus.

Lassen vermuten, dass, wenn wir uns bewegen Schildkröte 1 Schritt zu einer Zeit, und Hase 2 Schritte auf ein mal, Sie werden schließlich treffen sich an einem Punkt. Wir werden zeigen, dass zunächst diese Hypothese wahr ist.

Die Abbildung zeigt eine Liste mit einem Zyklus. Der Zyklus hat eine Länge von n und wir sind zunächst m Schritte Weg von den Zyklus. Auch lassen Sie uns sagen, dass der Treffpunkt ist k Schritte entfernt von der Zyklus-Anfang und die Schildkröte und der Hase trifft nach insgesamt i Schritte.

Den folgenden 2 Bedingungen halten muss:

1) i = m + p * n + k

2) 2i = m + q * n + k

Die erste sagt, dass die Schildkröte bewegt sich i Schritte und in diesen i Schritte, es ruft zuerst an den Zyklus. Dann geht es durch den Zyklus p Zeit für eine positive Zahl p. Schließlich geht es über k mehr Knoten, bis es erfüllt Hasen.

Einer ähnliches gilt für Hasen. Es bewegt sich 2i Schritte und in diesen 2i Schritte, es ruft zuerst an den Zyklus. Dann geht es durch den Zyklus q Zeit für eine positive Zahl q. Schließlich geht es über k mehr Knoten, bis Sie auf die Schildkröte.

Als Hase reist mit der doppelten Geschwindigkeit der Schildkröte, und die Zeit ist konstant für beide, wenn Sie erreichen den Treffpunkt.

So, mit einer einfachen Geschwindigkeit, Zeit und Distanz-relation,

2 ( m + p * n + k ) = m + q * n + k

=> 2m + 2pn + 2k = m + nq + k 

=>  m + k = ( q - 2p ) n

Unter den m, n, k, p, q, die ersten beiden sind die Eigenschaften der gegebenen Liste. Wenn wir zeigen können, dass es mindestens ein Satz von Werten für k, q, p, macht diese Gleichung wahr ist, wir zeigen, dass die Hypothese korrekt ist.

Einer solchen Lösung ist wie folgt:

p = 0

q = m

k = m n - m

Wir können bestätigen, dass diese Werte wie folgt:

m + k = ( q - 2p ) n  

=> m + mn - m = ( m - 2*0) n

=> mn = mn.

Für diesen Satz, i ist

i = m + p n + k

=> m + 0 * n + mn - m = mn.

Natürlich, Sie sollten sehen, dass dies nicht unbedingt die kleinste, die ich möglich. In anderen Worten, Schildkröte und Hase haben könnte, trafen sich bereits vor vielen Zeiten. Da wir allerdings zeigen, dass Sie treffen sich irgendwann mindestens einmal können wir sagen, dass die Hypothese korrekt ist. Also müssten Sie zu treffen, wenn wir bewegen Sie Schritt 1, und die anderen 2 Schritte auf einmal.

Wir können jetzt gehen Sie zum zweiten Teil des Algorithmus ist, wie zu finden, die Anfang des Zyklus.

Zyklus Anfang

Einmal die Schildkröte und der Hase treffen, lassen wir die Schildkröte zurück an den Anfang der Liste und halten Hasen, wo Sie sich trafen (die k Schritte von der Zyklus-Anfang).

Die Hypothese ist, dass, wenn wir uns von Ihnen bewegen sich mit der gleichen Geschwindigkeit (Schritt 1), das erste mal, dass Sie jemals wieder treffen wird der Zyklus Anfang.

Lasst uns beweisen, dass diese Hypothese.

Lasst uns zunächst annehmen, einige oracle-sagt uns, was m ist.

Dann, wenn wir uns von Ihnen bewegen sich die m + k Schritte, Schildkröte hätte, um an den Punkt gelangen, trafen Sie ursprünglich (k Schritte entfernt von der Zyklus-Anfang - in der Abbildung zu sehen).

Zuvor haben wir gezeigt, dass m + k = (q - 2p) n.

Da m + k Schritte ist ein Vielfaches des Zyklus der Länge n, der Hase, in der Zwischenzeit gehen würde, durch die Schleife (q-2p) Zeit und würden kommen wieder an den gleichen Punkt (k Schritte von der Zyklus-Anfang).

Nun, anstatt Sie verschieben m + k Schritte, wenn wir Sie lassen sich nur bewegen, m-Schritte, Schildkröte ankommen würde, auf der Zyklus-Anfang. Hasen gehen würden, werden k Schritte kurz vor dem Abschluss (q-2p) Rotationen. Da begann es k Schritte vor der Zyklus-Anfang, Hase müsste, kommen am Zyklus-Anfang.

Als Ergebnis dieser erklärt Ihnen, Sie hätten ein treffen am Zyklus-Anfang nach einigen Anzahl der Schritte für die erste Zeit (erste Zeit, weil die Schildkröte gerade angekommen auf der Zyklus nach m Schritten und konnte es nie sehen Hasen, die bereits im Zyklus).

Nun wissen wir, dass die Anzahl der Schritte, die wir brauchen, um Sie zu bewegen, bis Sie sich treffen stellt sich heraus, dass der Abstand vom Anfang der Liste der Zyklus-Anfang, m. Natürlich, der Algorithmus braucht nicht zu wissen, was m ist. Es wird nur bewegen Sie beide die Schildkröte und der Hase einen Schritt zu einer Zeit, bis Sie sich treffen. Der Treffpunkt ist um den Zyklus zu starten und die Anzahl der Schritte, muss der Abstand (m) nach der Zyklus-Anfang. Angenommen, wir kennen die Länge der Liste, können wir auch, berechnen Sie die Länge des Zyklus der Subtraktion von m aus der Liste Länge aus.

InformationsquelleAutor der Antwort CEGRD

_{Old Monk ist einfach und unter-Antwort von Ihnen positiv bewertet werden erklärt finden, der Zyklus, wenn die schnellen Läufer vervollständigt nur einzigen vollständigen Zyklus. In dieser Antwort, die ich erklären der Fall, wenn der schnelle Läufer hat ausgeführt, die Schleife mehrere Male, bevor die langsam-Läufer betritt die Schleife.}

Dasselbe Bild:

Sagen wir, der schnelle Läufer hat ausgeführt, die Schleife m mal, bevor Sie langsam und schnell erfüllen. Dies bedeutet, dass:

• Distanz laufen durch die langsamen: x + y
• Entfernung laufen, indem Sie fallen: x + m(y + z) + y D. H. zusätzliche ywo Sie sich treffen

Da schnelle Läufe mit zweimal die Geschwindigkeit langsam ist, und dass Sie schon laufen zur gleichen Zeit, es bedeutet, dass, wenn wir die doppelte Distanz lief langsam bekommen wir die Strecke verlief durch schnell. So,

• 2(x + y) = x + m(y + z) + y

Lösung für x gibt,

x = (m - 1)(y + z) + z

Im real-Szenario würde es bedeuten, x = (m - 1) komplette Schleife läuft + eine zusätzliche Entfernung z.

Daher, wenn wir setzen einen pointer auf den Anfang der Liste und lassen Sie die anderen am Treffpunkt, dann verschieben Sie von der gleichen Geschwindigkeit führt in der in-Schleife Zeiger Abschluss m - 1, läuft der loop und dann treffen die anderen Zeiger direkt an den loop-Anfang.

InformationsquelleAutor der Antwort displayName

Okay, so vermuten lässt der Hase und die Schildkröte treffen sich an einem Punkt, der k Schritte vom Beginn des Zyklus, die Anzahl der Schritte, bevor der Zyklus beginnt, wird mu und die Länge des Zyklus ist L.

Also nun an der Treffpunkt ->

Zurückgelegte Strecke Schildkröte = mu + a*L + k - Gleichung 1

(Schritte, die zum erreichen der zu Beginn des Zyklus + Schritte, die für die Abdeckung 'a' Iterationen des Zyklus + k Schritte vom start des Zyklus)
(wobei a eine positive Konstante)

Zurückgelegte Strecke der Hase = mu + b*L + k - Gleichung 2

(Schritte, die zum erreichen der zu Beginn des Zyklus + Schritte, die für die Abdeckung 'b' Iterationen des Zyklus + k Schritte vom start des Zyklus)
(wobei b eine positive Konstante und b>=a)

So dass die zusätzliche Distanz durch die Hase ist = Gleichung 2 - Gleichung 1 = (b-a)*L

Bitte beachten Sie, dass dieser Abstand auch gleich der Entfernung von der Schildkröte, von dem Ausgangspunkt, da der Hase bewegt sich 2-mal schneller als die Schildkröte. Dies kann gleichgesetzt werden 'mu+k', die auch die Entfernung der Treffpunkt vom Anfang, wenn wir nicht gehören mehrere Durchquerung des Zyklus.

So,
mu + k = (b-a)*L

So mu nur wenige Schritte von diesem Punkt führen würde, zurück an den Anfang des Zyklus (da k Schritte vom Anfang des Zyklus wurden bereits ergriffen, um zu erreichen den Treffpunkt). Dies könnte geschehen, in dem gleichen Zyklus oder nachfolgende Zyklen.
So, jetzt verschieben wir die Schildkröte zu Anfang der verknüpften Liste, wird es dauern, mu Schritten erreichen Sie den Ausgangspunkt des Zyklus und der Hase würde nehmen mu Schritten zu erreichen auch am Anfang des Zyklus und damit würden Sie beide treffen Sie auf den Ausgangspunkt des Zyklus.

P. S. Ehrlich gesagt, ich hatte die gleiche Frage wie der ursprüngliche poster in meinem Kopf, und ich lese die erste Antwort, Sie habe klar ein paar Sachen konnte ich aber nicht bekommen, um das endgültige Ergebnis klar und so versuchte ich, es zu tun, meinen eigenen Weg und finden es leichter zu verstehen.

InformationsquelleAutor der Antwort Prateek Jassal

Ansatz:

Gibt es zwei Zeiger:

• Eine langsame Zeiger, bewegt sich ein Knoten zu einem Zeitpunkt.
• Eine schnelle Zeiger, zieht zwei Knoten zu einem Zeitpunkt.

Wenn die beiden Zeiger aufeinander treffen, beweist, dass es eine Schleife. Sobald Sie getroffen haben, einen der Knoten auf den Kopf und dann haben beide gehen von einem Knoten zu einem Zeitpunkt. Sie treffen sich am Anfang der Schleife.

Begründung:
Wenn sich zwei Menschen Spaziergang entlang einer Kreisbahn, einer von Ihnen mit zweimal der Geschwindigkeit der anderen, wo Sie sich treffen? Genau wo Sie gestartet.

Nehmen wir nun an, der schnelle Läufer hat einen Vorsprung von k Schritte in eine n Schritt Schoß. wo werden Sie sich treffen? Genau an n-k Schritte. Bei dem langsamen Läufer gedeckt hat (n-k) Schritte, die schneller Läufer würde abgedeckt haben k+2(n-k) Schritte.
(dh k+2n-2k Schritte ie 2n-k Schritte). also(n-k) Schritte (Der Pfad ist kreisförmig, und wir sind nicht besorgt über die Anzahl der Runden, nach denen Sie sich treffen; Wir sind nur daran interessiert, die position wo Sie sich treffen).

Nun, wie konnte der schnelle Läufer Holen den Vorsprung von k Schritte in den ersten Platz? Da nahm es die langsamen Läufer, die viele Stufen zum erreichen der Anfang der Schleife. So der Anfang der Schleife ist k Schritte von dem head-Knoten.

Hinweis: dem Knoten, auf Dem beide Zeiger erfüllt ist k Schritte vom Beginn der Schleife (in der Schleife) und dem head-Knoten ist auch k Schritte entfernt vom Anfang der Schleife. Wenn wir also Zeiger voran bei gleichem Tempo der 1 Schritt von bot diese Knoten, Sie treffen sich am Anfang der Schleife.

Ich glaube, es ist einfach. Bitte lassen Sie mich wissen, wenn ein Teil mehrdeutig ist.

InformationsquelleAutor der Antwort Aadith

Es ist eigentlich leicht zu beweisen, dass Sie beide treffen sich auf den Ausgangspunkt, wenn man die Mathematik hinter der Treffpunkt.

Zunächst lassen Sie m bezeichnen den Ausgangspunkt des Zyklus, in der verknüpften Liste , und n bezeichnen die Länge des Zyklus . Dann der Hase und die Schildkröte zu treffen , haben wir :

( 2*t - m )%n = (t - m) %n, where t = time (at t = 0 , both are at the start)

Besagt das mehr mathematisch :

(2*t - m - (t - m) ) = 0 modulo n , which implies , t = 0 modulo n 

also Sie treffen sich zur Zeit t die sollte ein Vielfaches der Länge des Zyklus . Dies bedeutet, dass Sie treffen an einem Ort, der
(t-m) modulo n = (0-m) modulo n = (-m) modulo n .

So, jetzt kommen wir zurück zu der Frage , ob Sie einen Zeiger vom Anfang der verketteten Liste , und zum anderen aus dem Schnittpunkt , nach m Schritten haben wir die Hasen (die sich innerhalb des Zyklus) kommen zu einem Punkt die ((-m) + m) modulo n = 0 modulo n das ist nichts anderes als der Ausgangspunkt des Zyklus.So können wir sehen, dass nach m Schritten kommt es zu Beginn des Zyklus und die Schildkröte treffen, es gibt, wie es durchziehen wird m Schritte vom Anfang der verketteten Liste.

Als Seite beachten ,können wir auch die Zeit berechnen, die von Ihrem Schnittpunkt auf diese Weise : Der Zustand t = 0 modulo n sagt uns, dass das treffen in einer Zeit, die einem vielfachen der Zyklus-Länge , und auch t sollte größer sein als mwie Sie entsprechen würde in den Zyklus . So dass die Zeit genommen wird, wird gleich die erste von mehreren ndie größer ist als m .

InformationsquelleAutor der Antwort user1011

können sagen,

N[0] is the node of start of the loop, 
m is the number of steps from beginning to N[0].

wir haben 2 Zeiger A und B, A läuft mit 1x Geschwindigkeit, B auf 2x Geschwindigkeit, sowohl am Anfang beginnen.

beim Einen erreicht N[0], B sollte bereits in N[m].
(Hinweis: Ein m Schritte, um zu erreichen, N[0], und B sollte m Schritte weiter)

Dann läuft k-weitere Schritte zu kollidieren, B,
d.h. A ist bei N[k], B N[m+2k]
(Hinweis: B sollte läuft für 2k-Schritten ausgehend von N[m])

Einem prallen B-N[k] und N[m+2k] beziehungsweise, es bedeutet
k=m+2k, also k = -m

So, um den Zyklus wieder auf N[0] N[k], müssen wir m mehr Schritte.

Einfach zu sagen, wir müssen Sie nur ausführen, m mehr Schritte nach fanden wir den Kollision-node. Wir können einen Zeiger zu laufen von Anfang an und ein Zeiger läuft aus der Kollision Knoten, Sie treffen sich zu N[0] nach m Schritten.

Daher der pseudo-code ist wie folgt:

1) A increase 1 step per loop
2) B increase 2 steps per loop
3) if A & B are the same node, cycle found, then go to 5
4) repeat from 1
5) A reset to head
6) A increase 1 step per loop
7) B increase 1 step per loop
8) if A & B are the same node, start of the cycle found
9) repeat from 6

InformationsquelleAutor der Antwort phdfong - Kenneth Fong

Eine einfache Erklärung mit der Idee der relative Geschwindigkeit lehrte in der high school - Physik 101 /Kinematik Vorträge.

1. Nehmen wir Abstand vom Anfang der verknüpften Liste zu starten, der Kreis ist x Hopfen. Nennen wir den start der Kreis als Punkt X (in caps - siehe Abbildung oben). Auch wir übernehmen die volle Größe des Kreises ist N Hopfen.

2. Geschwindigkeit von Hase = 2 * Geschwindigkeit der Schildkröte. So, dass ist 1 hops/sec und 2 hops/sec bzw.

3. Wenn die Schildkröte erreicht das starten des Kreises Xdie Hasen müssen weiter x hops entfernt am Punkt Y in der Abbildung. (Weil Hase reiste zweimal in die Ferne, wie die Schildkröte).

4. So, die Länge der übrigen Bogen im Uhrzeigersinn von X nach Y wäre N-x. Tseine zufällig auch die relative Distanz abgedeckt werden, die zwischen der Hase und die Schildkröte für Sie erfüllen zu können. Lassen Sie uns sagen, diese relative Distanz in der Zeit t_m D. H. die Zeit, zu treffen. Die Relative Geschwindigkeit ist (2 hops/sec - 1 hops/sec) d.h. 1 hops/sec. Also mit, relativer Abstand = relative Geschwindigkeit X Zeit, die wir erhalten, t = N-x Sek. So dauert es N-x zu erreichen ist der Treffpunkt für die Schildkröte und der Hase.

5. Nun in N-x Sek Zeit und bei 1 hops/sec speed, die Schildkröte, die war früher bei Punkt X wird die N-x-hops zum erreichen des meeting point M. Also, das heißt, der Treffpunkt M ist bei N-x Hopfen gegen den Uhrzeigersinn von X = (was weiter impliziert) => dass es x Verbleibende Entfernung vom Punkt M zu X im Uhrzeigersinn.

6. Aber x ist auch der Abstand zu erreichen, zeigen X vom Anfang der verketteten Liste.

7. Nun, wir kümmern uns nicht, was die Anzahl der hops x entspricht. Wenn wir eine Schildkröte am Anfang der LinkedList und eine Schildkröte am Treffpunkt M und lassen Sie Sie hüpfen/gehen, dann werden Sie treffen sich an Punkt Xdie den Punkt (oder Knoten), die wir brauchen.

InformationsquelleAutor der Antwort Pranjal Mittal

Es ist ein Fehler in die meisten Lösungen für dieses problem. Was ist, wenn der Letzte Knoten war mit dem ersten verbunden, und es war einfach eine Schleife? Was, wenn langsam und schnell trafen sich am Kopf der Schleife das erste mal?
Sie wäre nicht die richtige Antwort zu finden mit dieser Lösung.
Es gibt eine richtige Antwort auf die Frage, wie Sie diese situation vermeiden, aber angesichts der glücklichen Pfad, mit einer Anzahl an Knoten k vor der Schleife, hier ist eine einfache Erklärung:
(wenn Sie mehr wissen möchten über die real, verallgemeinerte Lösung, ping me)

-es gibt k Schritte vor dem loop. Wir wissen nicht, was k ist, und nicht brauchen, um das herauszufinden. Wir arbeiten Abstrakt mit nur k.

--Nach k Schritten

----- T ist bei Zyklus-Anfang

----- H k Schritte in Zyklus (er ging insgesamt 2k und somit k in der Schleife)

** Sie sind nun loopsize - k neben

(beachten Sie, dass k == K == mod(loopsize, k) --z.B. wenn ein Knoten ist 2 Schritte in eine 5 Knoten Zyklus ist auch 7, 12 oder 392 Schritte, also wie groß ist der Zyklus w.r.t k nicht Faktor bei der.

Da Sie zu fangen, zu einander in der Höhe von 1 Schritt pro Einheit von Zeit, weil man sich doppelt so schnell wie die anderen, Sie treffen sich auf loopsize - k.

Dies bedeutet, dass es dauern wird, k Knoten zu erreichen, der Anfang des Zyklus und damit der Abstand von Kopf bis cyclestart und Kollision cyclestart sind die gleichen.

So, jetzt nach der ersten Kollision bewegen T zurück zum Kopf. T und H treffen an der cyclestart, wenn Sie sich bewegen bei der rate von 1 pro. (in k Schritten)

Dies bedeutet, dass der Algorithmus:

• von Kopf bewegen T = t.nächsten und H. weiter.weiter, bis Sie zusammenstoßen ( T == H) (es ist ein Zyklus)

//kümmern sich um den Fall, wenn k=0 oder T und H trafen sich am Kopf der Schleife durch
die Berechnung der Länge der Schleife

--count die Länge des Zyklus durch verschieben von T oder H, um es mit einem Zähler

--der Mauszeiger T2 auf den Kopf der Liste

--bewegen Sie den Zeiger Länge des Zyklus Schritte

--bewegen Sie einen anderen Zeiger H2-an-Kopf -

--verschieben von T2 und H2 im tandem, bis Sie sich treffen, am Anfang des Zyklus

das ist es!

InformationsquelleAutor der Antwort Droid Teahouse