Algorytm wykrywania cyklu Floyda Określenie punktu początkowego cyklu

Szukam pomocy w zrozumieniu algorytmu wykrywania cyklu Floyda. Przeszedłem wyjaśnienie na Wikipedii ( http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare )

Widzę, jak algorytm wykrywa cykl w czasie O (n). Nie jestem jednak w stanie wyobrazić sobie, że kiedy wskaźniki żółwia i zająca spotkają się po raz pierwszy, początek cyklu można ustalić, przesuwając wskaźnik żółwia z powrotem, aby rozpocząć, a następnie przesuwając zarówno żółwia, jak i zająca, o krok. Punktem, w którym spotykają się po raz pierwszy, jest początek cyklu.

Czy ktoś może pomóc, podając wyjaśnienie, które, mam nadzieję, różni się od tego na Wikipedii, ponieważ nie jestem w stanie go zrozumieć / wizualizować?

Możesz odwołać się do „Wykrywanie początku pętli na pojedynczo połączonej liście” , oto fragment:

Przebyty dystans slowPointerprzed spotkaniem $= x+y$

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

Ponieważ fastPointerpodróżuje z podwójną prędkością slowPointer, a czas jest stały dla obu, gdy dotrą do miejsca spotkania. Używając prostej relacji prędkości, czasu i odległości ( slowPointerprzebytej połowy odległości):

W związku z tym, przechodząc slowPointerna początek listy połączonej i wykonując oba slowPointeroraz fastPointerprzesuwając jeden węzeł na raz, oba mają taką samą odległość do pokonania .

Dotrą do punktu, w którym pętla zaczyna się na połączonej liście.

Widziałem zaakceptowaną odpowiedź jako dowód również w innym miejscu. Jednak chociaż jest łatwy do odczytania, jest niepoprawny. Dowodzi tego

$x = z$

To, co naprawdę chcesz udowodnić, to (używając tych samych zmiennych, jak opisano na schemacie w zaakceptowanej odpowiedzi powyżej):

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

$(y + z)$$L$

więc chcemy udowodnić:

$z = x\ mod\ L$

Lub że z jest zgodne z x (modulo L)

Poniższy dowód ma dla mnie większy sens:

$M = x + y$

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

$x + y = kL$

$x = kL - y$

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

Znalazłem odpowiedź na stackoverflow. Dzięki, jeśli ktoś szukał tego dla mnie. A dla tych, którzy tak jak ja chcieli wyjaśnienia, proszę zapoznać się z: https://stackoverflow.com/questions/3952805/proof-of-detecting-the-start-of-cycle-in-linked-list Wybrana odpowiedź na pytanie, wyjaśnia to!