Linked List Loop Detection

Question

Wie können wir beweisen, dass die Bewegung schnell und langsam Zeiger (von Anfang an) macht 1 gibt es Treffpunkt der Schleife Knoten? Ich meine ich kann nicht verstehen, was gibt es eine garantierte Lösung, die der Meeting-Knoten ist die Schleife Knoten (dh Knoten, von wo Zyklus startet)
Ich bin klar mit Schildkröte Hase-Loop-Erkennung im Grunde ich spreche über detekting den Knoten, wo Zyklus beginnt, nachdem Schleife wurde erkannt.

Answer 1

Es ist ein sehr einfacher Beweis wirklich. Zuerst beweisen Sie, dass der langsame Zeiger nach fast n + k Schritten mit dem schnellen Zeiger übereinstimmt, wobei n die Anzahl der Verbindungen zum Beginn des Zyklus und k die Länge des Zyklus ist. Und dann beweisen Sie, dass sie nach genau k weiteren Schritten wieder zusammenpassen.

Der Punkt, wo sie sich treffen, ist überall im Zyklus.

Answer 2

Bevor Sie dies formal beweisen, sollten Sie sich zunächst ein Beispiel ansehen, damit Sie ein intuitiveres Verständnis davon bekommen und visualisieren können, was vor sich geht. Angenommen, Sie haben die folgende verknüpften Liste haben, in denen die 3 (bei Index 3) verweist zurück auf die 1 (bei Index 1):

[0| ]->[1| ]->[2| ]->[3| ]--+ 
     ^    | 
     |     | 
     |     | 
     +------------------+ 

Ein Spaziergang durch die logische Weiterentwicklung, können Sie folgende Punkte beachten, wenn langsam erhöht wird durch eine Position und schnell durch zwei:

1. langsam = Index 0; schnell = Index 0
2. langsam = Index 1; schnell = Index 2
3. langsam = Index 2; schnell = Index 1
4. langsam = Index 3; schnell = Index 3 (Schleife existiert)

Hoffe, das hilft!