Algoritmo de detecção do ciclo de Floyd | Determinando o ponto inicial do ciclo

Estou procurando ajuda para entender o algoritmo de detecção de ciclo de Floyd. Passei pela explicação na wikipedia ( http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare )

Eu posso ver como o algoritmo detecta o ciclo em O (n) tempo. No entanto, não consigo visualizar o fato de que, uma vez que os ponteiros da tartaruga e da lebre se encontram pela primeira vez, o início do ciclo pode ser determinado movendo o ponteiro da tartaruga de volta para o início e movendo a tartaruga e a lebre um passo de cada vez. O ponto em que eles se conheceram é o início do ciclo.

Alguém pode ajudar, fornecendo uma explicação, espero que diferente da da wikipedia, pois não consigo entender / visualizar?

Você pode consultar "Detectando o início de um loop na lista vinculada individual" , eis um trecho:

Distância percorrida slowPointerantes da reunião $= x+y$

Distância percorrida fastPointerantes da reunião $=(x + y + z) + y$ = x + 2y + z

Uma vez que fastPointerviaja com o dobro da velocidade de slowPointer, e o tempo é constante para ambos quando atingem o ponto de encontro. Então, usando simples relação de velocidade, tempo e distância ( slowPointerpercorreu metade da distância):

Portanto, movendo slowPointer- se para o início da lista vinculada, criando os dois slowPointere fastPointermovendo um nó de cada vez, ambos têm a mesma distância a percorrer .

Eles chegarão no ponto em que o loop inicia na lista vinculada.

Também já vi a resposta aceita como prova em outro lugar. No entanto, embora seja fácil de grok, ele está incorreto. O que prova é

$x = z$ (que está obviamente errado, e o diagrama apenas faz com que pareça plausível devido à maneira como é esboçado).

O que você realmente deseja provar é (usando as mesmas variáveis ​​descritas no diagrama na resposta aceita acima):

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

$(y + z)$$L$

então, o que queremos provar é:

$z = x\ mod\ L$

Ou que z é congruente com x (módulo L)

A prova a seguir faz mais sentido para mim:

$M = x + y$

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

$x + y = kL$

$x = kL - y$

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

Encontrei a resposta no stackoverflow. Obrigado se alguém estava olhando para mim. E para aqueles que como eu queriam uma explicação, consulte: https://stackoverflow.com/questions/3952805/proof-of-detecting-the-start-of-cycle-in-linked-list A resposta escolhida para o pergunta, explica isso!