Позвольте мне попытаться уточнить свои алгоритмы обнаружения цикла, которые предоставляются в http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare.
Я ссылаюсь на цифру 
в моем объяснении.
Как это работает
Давайте возьмем черепаху и зайца (название указателей), указывающих на начало списка с циклом.
Давайте предположим, что, если мы будем перемещать черепаху по 1 шагу за раз, а по 2 шага за раз, они в конечном итоге встретятся в определенный момент. Покажем, что в первую очередь эта гипотеза верна.
На рисунке показан список с циклом. Цикл имеет длину n, и мы изначально на m шагах от цикла. Также предположим, что место встречи находится в k шагах от начала цикла, а черепаха и заяц встречаются после всего i шагов.
Должны соблюдаться следующие 2 условия:
1) i = m + p * n + k
2) 2i = m + q * n + k
Первый говорит, что черепаха движется на i шагов, и на этих i шагах она сначала попадает в цикл. Затем он проходит цикл p раз для некоторого положительного числа p. Наконец, он проходит через k больше узлов, пока не встретит зайца.
Аналогичное верно для зайца. Он перемещается на 2i шага, и на этих 2i шагах он сначала попадает в цикл. Затем он проходит цикл q раз для некоторого положительного числа q. Наконец, он проходит через k больше узлов, пока не встретит черепаху.
Поскольку заяц путешествует с удвоенной скоростью черепахи, и время для обоих постоянное, когда они достигают места встречи.
Итак, используя простое соотношение скорости, времени и расстояния,
2 ( m + p * n + k ) = m + q * n + k
=> 2m + 2pn + 2k = m + nq + k
=> m + k = ( q - 2p ) n
Среди m, n, k, p, q первые два являются свойствами данного списка. Если мы можем показать, что существует хотя бы один набор значений для k, q, p, который делает это уравнение верным, мы покажем, что гипотеза верна.
Один такой набор решений выглядит следующим образом:
p = 0
q = m
k = m n - m
Мы можем проверить, что эти значения работают следующим образом:
m + k = ( q - 2p ) n
=> m + mn - m = ( m - 2*0) n
=> mn = mn.
Для этого набора i равно
i = m + p n + k
=> m + 0 * n + mn - m = mn.
Конечно, вы должны видеть, что это не обязательно наименьшее из возможных. Другими словами, черепаха и заяц могли встречаться уже много раз. Однако, поскольку мы показываем, что они встречаются в какой-то момент хотя бы раз, мы можем сказать, что гипотеза верна. Поэтому им придется встретиться, если мы переместим одного из них на 1 шаг, а другого - на 2 шага за раз.
Теперь мы можем перейти ко второй части алгоритма, которая заключается в том, как найти начало цикла.
Начало цикла
После того, как черепаха и заяц встретятся, давайте вернем черепаху в начало списка и оставим зайца там, где он встретился (это k шагов от начала цикла).
Гипотеза состоит в том, что если мы позволим им двигаться с одинаковой скоростью (1 шаг для обоих), то в первый раз, когда они снова встретятся, начнется цикл.
Давайте докажем эту гипотезу.
Давайте сначала предположим, что какой-то оракул говорит нам, что такое m.
Тогда, если мы позволим им двигаться m + k шагов, черепаха должна прибыть в точку, с которой они встречались изначально (k шагов от начала цикла - см. На рисунке).
Ранее мы показали, что m + k = (q - 2p) n.
Поскольку m + k шагов кратно длине цикла n, заяц за это время прошел бы цикл (q-2p) раз и вернулся бы к той же точке (k шагов от начала цикла) ).
Теперь, вместо того, чтобы позволить им двигаться m + k шагов, если мы позволим им двигаться только m шагов, черепаха прибудет в начало цикла. Заяц может пройти на k шагов меньше, чем завершение (q-2p) поворотов. Поскольку он начал k шагов перед началом цикла, заяц должен был прийти к началу цикла.
В результате это объясняет, что им придется встречаться в начале цикла после некоторого количества шагов в первый раз (в самый первый раз, потому что черепаха только что прибыла в цикл после m шагов, и она никогда не могла видеть был уже в цикле).
Теперь мы знаем, что количество шагов, которое нам нужно переместить, пока они не встретятся, оказывается расстоянием от начала списка до начала цикла, м. Конечно, алгоритм не должен знать, что такое m. Он будет просто перемещать черепаху и зайца по одному шагу за раз, пока они не встретятся. Место встречи должно быть началом цикла, а количество шагов - расстоянием (м) до начала цикла. Предполагая, что мы знаем длину списка, мы также можем вычислить длину цикла вычитания m из длины списка.