Algorithme de détection de cycle de Floyd | Déterminer le point de départ du cycle

Je cherche de l'aide pour comprendre l'algorithme de détection de cycle de Floyd. J'ai parcouru l'explication sur wikipedia ( http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare )

Je peux voir comment l'algorithme détecte le cycle en temps O (n). Cependant, je ne peux pas visualiser le fait qu'une fois que les pointeurs de tortue et de lièvre se rencontrent pour la première fois, le début du cycle peut être déterminé en déplaçant le pointeur de la tortue pour commencer, puis en déplaçant la tortue et le lièvre une étape à la fois. Le point où ils se rencontrent pour la première fois est le début du cycle.

Quelqu'un peut-il m'aider en fournissant une explication, si tout va bien différente de celle sur wikipedia, car je ne peux pas la comprendre / la visualiser?

Vous pouvez vous référer à "Détection du début d'une boucle dans une liste liée individuellement" , voici un extrait:

Distance parcourue slowPointeravant la rencontre $= x+y$

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

Depuis fastPointervoyage avec le double de la vitesse slowPointeret le temps est constant pour les deux lorsque le point de rencontre atteint. Donc, en utilisant une relation simple de vitesse, de temps et de distance ( slowPointerparcouru la moitié de la distance):

Par conséquent, en se déplaçant slowPointerau début de la liste chaînée, en faisant les deux slowPointeret fastPointeren déplaçant un nœud à la fois, ils ont tous deux la même distance à parcourir .

Ils atteindront le point où la boucle commence dans la liste chaînée.

J'ai vu la réponse acceptée comme preuve ailleurs aussi. Cependant, bien qu'il soit facile à grogner, il est incorrect. Ce que cela prouve, c'est

$x = z$

Ce que vous voulez vraiment prouver, c'est (en utilisant les mêmes variables que celles décrites dans le diagramme dans la réponse acceptée ci-dessus):

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

$(y + z)$$L$

donc, ce que nous voulons prouver, c'est:

$z = x\ mod\ L$

Ou que z est congru à x (modulo L)

La preuve suivante a plus de sens pour moi:

$M = x + y$

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

$x + y = kL$

$x = kL - y$

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

J'ai trouvé la réponse sur stackoverflow. Merci si quelqu'un cherchait ça pour moi. Et pour ceux qui comme moi voulaient une explication, veuillez vous référer à: https://stackoverflow.com/questions/3952805/proof-of-detecting-the-start-of-cycle-in-linked-list La réponse choisie à la question, explique-t-il!