Алгоритм обнаружения цикла Флойда | Определение начальной точки цикла

Я ищу помощь в понимании алгоритма обнаружения цикла Флойда. Я прошел объяснение в Википедии ( http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare )

Я могу видеть, как алгоритм обнаруживает цикл в O (N) времени. Однако я не могу представить себе тот факт, что как только указатели черепахи и зайца встречаются в первый раз, начало цикла можно определить, переместив указатель черепахи обратно, чтобы запустить, а затем переместив черепаху и зайца по одному шагу за раз. Точка, где они впервые встречаются, является началом цикла.

Может ли кто-нибудь помочь, предоставив объяснение, которое, я надеюсь, отличается от того, которое есть в Википедии, поскольку я не могу понять / представить его?

Вы можете обратиться к «Обнаружение начала цикла в односвязном списке» , вот выдержка:

Расстояние, пройденное slowPointerдо встречи $= x+y$

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

Так как fastPointerпутешествует с удвоенной скоростью slowPointer, и время постоянно для обоих, когда достигают места встречи. Итак, используя простое соотношение скорости, времени и расстояния ( slowPointerпройденное на половину расстояния):

Следовательно, перемещаясь slowPointerк началу связанного списка, делая оба slowPointerи fastPointerперемещая один узел за раз, они оба имеют одинаковое расстояние для покрытия .

Они достигнут точки, где цикл начинается в связанном списке.

Я видел принятый ответ как доказательство и в других местах. Однако, хотя его легко уловить, это неверно. Что это доказывает

$x = z$

То, что вы действительно хотите доказать, это (используя те же переменные, которые описаны в диаграмме в принятом ответе выше):

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

$(y + z)$$L$

Итак, что мы хотим доказать:

$z = x\ mod\ L$

Или что z конгруэнтно х (по модулю L)

Следующее доказательство имеет больше смысла для меня:

$M = x + y$

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

$x + y = kL$

$x = kL - y$

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

Я нашел ответ на stackoverflow. Спасибо, если кто-то изучал это для меня. А для тех, кто, как я хотел получить объяснение, пожалуйста, обратитесь к: https://stackoverflow.com/questions/3952805/proof-of-detecting-the-start-of-cycle-in-linked-list Выбранный ответ на вопрос, это объясняет!