Algoritma deteksi siklus Floyd | Menentukan titik awal siklus

Saya mencari bantuan untuk memahami algoritma pendeteksian siklus Floyd. Saya telah membaca penjelasan di wikipedia ( http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare )

Saya dapat melihat bagaimana algoritma mendeteksi siklus dalam waktu O (n). Namun, saya tidak dapat memvisualisasikan fakta bahwa setelah kura-kura dan kelinci bertemu untuk pertama kalinya, permulaan siklus dapat ditentukan dengan menggerakkan penunjuk kura-kura kembali untuk memulai dan kemudian memindahkan kura-kura dan kelinci satu langkah pada satu waktu. Titik pertemuan pertama mereka adalah awal siklus.

Dapatkah seseorang membantu dengan memberikan penjelasan, semoga berbeda dari yang ada di wikipedia, karena saya tidak dapat memahami / memvisualisasikannya?

Anda dapat merujuk ke "Mendeteksi awal loop dalam daftar yang ditautkan sendiri" , berikut adalah kutipannya:

Jarak yang ditempuh slowPointersebelum pertemuan $= x+y$

fastPointer $=(x + y + z) + y$

Karena fastPointerperjalanan dengan kecepatan dua kali lipatslowPointer , dan waktu adalah konstan untuk keduanya ketika mencapai titik pertemuan. Jadi dengan menggunakan hubungan kecepatan, waktu dan jarak yang sederhana ( slowPointermenempuh setengah jarak):

Oleh karena itu dengan bergerak slowPointeruntuk memulai daftar tertaut, dan membuat keduanya slowPointerdan fastPointeruntuk memindahkan satu simpul pada satu waktu, mereka berdua memiliki jarak yang sama untuk menutupi .

Mereka akan mencapai pada titik di mana loop dimulai pada daftar yang ditautkan.

Saya telah melihat jawaban yang diterima sebagai bukti di tempat lain juga. Namun, meskipun mudah untuk grok, itu tidak benar. Apa buktinya

$x = z$

Apa yang benar-benar ingin Anda buktikan adalah (menggunakan variabel yang sama seperti yang dijelaskan dalam diagram pada jawaban yang diterima di atas):

$z = x\ mod\ (y + z)$

$(y + z)$$L$

jadi, yang ingin kita buktikan adalah:

$z = x\ mod\ L$

Atau z itu kongruen dengan x (modulo L)

Bukti berikut lebih masuk akal bagi saya:

$M = x + y$

$2(x + y) = M + kL$$k$$x + y$$L$

$x + y = kL$

$x = kL - y$

$x$$L$$y$$M$$x + y$

Saya menemukan jawabannya di stackoverflow. Terima kasih jika ada yang mencari ini untuk saya. Dan bagi mereka yang menyukai saya ingin penjelasan, silakan merujuk ke: https://stackoverflow.com/questions/3952805/proof-of-detecting-the-start-of-cycle-in-linked-list Jawaban yang dipilih untuk pertanyaan, jelaskan!