Algoritmo de detección del ciclo de Floyd | Determinar el punto de inicio del ciclo

Estoy buscando ayuda para comprender el algoritmo de detección de ciclo de Floyd. He revisado la explicación en wikipedia ( http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare )

Puedo ver cómo el algoritmo detecta el ciclo en el tiempo O (n). Sin embargo, no puedo visualizar el hecho de que una vez que los punteros de la tortuga y la liebre se encuentran por primera vez, el inicio del ciclo se puede determinar moviendo el puntero de la tortuga hacia atrás para comenzar y luego moviendo la tortuga y la liebre un paso a la vez. El punto donde se encuentran por primera vez es el comienzo del ciclo.

¿Alguien puede ayudar proporcionando una explicación, con suerte diferente a la de wikipedia, ya que no puedo entenderla / visualizarla?

Puede consultar "Detectar el inicio de un bucle en una lista individualmente vinculada" , aquí hay un extracto:

Distancia recorrida slowPointerantes de la reunión $= x+y$

Distancia recorrida fastPointerantes de la reunión $=(x + y + z) + y$ = x + 2y + z

Ya que fastPointerviaja con el doble de velocidad slowPointer, y el tiempo es constante para ambos cuando llegan al punto de encuentro. Entonces, usando una relación simple de velocidad, tiempo y distancia ( slowPointerrecorrió la mitad de la distancia):

Por lo tanto, moviéndose slowPointeral inicio de la lista vinculada y haciendo ambos slowPointery fastPointerpara mover un nodo a la vez, ambos tienen la misma distancia que cubrir .

Llegarán al punto donde comienza el ciclo en la lista vinculada.

También he visto la respuesta aceptada como prueba en otro lugar. Sin embargo, si bien es fácil de asimilar, es incorrecto. Lo que prueba es

$x = z$ (lo cual obviamente es incorrecto, y el diagrama solo lo hace verosímil debido a la forma en que está esbozado).

Lo que realmente quiere probar es (usando las mismas variables que se describen en el diagrama en la respuesta aceptada arriba):

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

$(y + z)$$L$

entonces, lo que queremos probar es:

$z = x\ mod\ L$

O que z es congruente con x (módulo L)

La siguiente prueba tiene más sentido para mí:

$M = x + y$

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

$x + y = kL$

$x = kL - y$

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

Encontré la respuesta en stackoverflow. Gracias si alguien estaba investigando esto por mí. Y para aquellos que como yo quería una explicación, consulte: https://stackoverflow.com/questions/3952805/proof-of-detecting-the-start-of-cycle-in-linked-list La respuesta elegida a la pregunta, lo explica!