Я понимаю, что встреча Черепахи и Зайца завершает существование петли, но как перемещение черепахи в начало связанного списка при сохранении зайца в месте встречи с последующим перемещением обоих по одному шагу за раз заставляет их встретиться в начальной точке цикла?
algorithm
linked-list
cycle
floyd-cycle-finding
Страстный программист
источник
источник
Ответы:
Это алгоритм Флойда для обнаружения цикла . Вы спрашиваете о второй фазе алгоритма - как только вы нашли узел, который является частью цикла, как найти начало цикла?
В первой части алгоритма Флойда заяц перемещается на два шага за каждый шаг черепахи. Если черепаха и заяц когда-либо встречаются, существует цикл, и точка встречи является частью цикла, но не обязательно первым узлом в цикле.
Когда черепаха и заяц встречаются, мы нашли наименьшее i (число шагов, предпринятых черепахой), такое, что X i = X 2i . Пусть mu представляет количество шагов, которые нужно пройти от X 0 до начала цикла, и пусть lambda представляет длину цикла. Тогда i = mu + a лямбда и 2i = mu + b лямбда, где a и b - целые числа, обозначающие, сколько раз черепаха и заяц проходили цикл. Вычитание первого уравнения из второго дает i = (ba) * lambda, так что i - целое число, кратное lambda. Следовательно, X i + mu = X mu . X i представляет собой место встречи черепахи и зайца. Если вы переместите черепаху обратно в начальный узел X0 , и пусть черепаха и заяц продолжат с той же скоростью, после дополнительных шагов mu черепаха достигнет X mu , а заяц достигнет X i + mu = X mu , поэтому вторая точка встречи обозначает начало цикл.
источник
X_mu
начала цикла (по определению мю). Затем, если вы сделаете еще i шагов, где i кратно длине цикла, вы вернетесь обратно к началу цикла:X_mu + i
=X_mu
. Но сложение является коммутативным, так что это равносильно выполнению i шагов, чтобы добраться от начала до первой точки встречиX_i
, а затем дополнительных шагов, чтобы вернуться кX_mu
началу цикла.i
находится в некоторой точке цикла, я думаю, что уравнение должно бытьi = mu + k + a*lambda
и2i = mu + k + b*lambda
гдеk
число шагов от начала цикла до точки встречи. Вычитание обоих уравнений дает один и тот же результат.Позвольте мне попытаться пояснить алгоритм обнаружения циклов, который представлен на http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare своими собственными словами.
Как это устроено
Давайте возьмем черепаху и зайца (название указателей), указывающих на начало списка с циклом, как на диаграмме выше.
Давайте предположим, что если мы будем перемещать черепаху по 1 шагу за раз, а заячь по 2 шага за раз, они в конечном итоге встретятся в определенный момент. Покажем, что в первую очередь эта гипотеза верна.
На рисунке показан список с циклом. Цикл имеет длину,
n
и мы изначальноm
отходим от цикла. Также допустим, что место встречи находится в несколькихk
шагах от начала цикла, и черепаха встречается, когда черепаха предпринялаi
полные шаги. (К тому времени заяц предпринял бы2i
полные шаги.)Должны соблюдаться следующие 2 условия:
Первый говорит, что черепаха двигает
i
шаги, и на этихi
шагах она сначала попадает в цикл. Затем он проходит время циклаp
для некоторого положительного числаp
. Наконец, он проходитk
больше узлов, пока не встретит зайца.Аналогичное верно для зайца. Он перемещает
2i
шаги, и на этих2i
шагах он сначала попадает в цикл. Затем он проходит время циклаq
для некоторого положительного числаq
. Наконец, он проходит черезk
несколько узлов, пока не встретит черепаху.Поскольку заяц путешествует с удвоенной скоростью черепахи, и время одинаково для обоих, когда они достигают места встречи.
Таким образом, используя простое соотношение скорости, времени и расстояния,
Среди m, n, k, p, q первые два являются свойствами данного списка. Если мы можем показать, что существует хотя бы один набор значений для k, q, p, который делает это уравнение истинным, мы покажем, что гипотеза верна.
Один такой набор решений выглядит следующим образом:
Мы можем проверить, что эти значения работают следующим образом:
Для этого набора
i
естьКонечно, вы должны видеть, что это не обязательно наименьшее из возможных. Другими словами, черепаха и заяц могли встречаться уже много раз. Однако, поскольку мы показываем, что они встречаются в какой-то момент хотя бы раз, мы можем сказать, что гипотеза верна. Так что им придется встретиться, если мы переместим одного из них на 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. Он будет просто перемещать черепаху и зайца по одному шагу за раз, пока они не встретятся. Место встречи должно быть началом цикла, а число шагов должно быть расстоянием (м) до начала цикла. Предполагая, что мы знаем длину списка, мы также можем вычислить длину цикла вычитания m из длины списка.
источник
m + k = (q - 2p) n
может быть дополнительно упрощено доm + k = q*n
. Это связано с тем, что число петель, которые берет черепаха, всегда будет равно нулю, поскольку заяц никогда не сможет обогнать черепаху, не встретив ее. Подумай об этом.Посмотрите это изображение:
Расстояние, пройденное по slowPointer до встречи = x + y
Расстояние, пройденное fastPointer до встречи = (x + y + z) + y = x + 2y + z
Так как fastPointer перемещается с удвоенной скоростью slowPointer, и время для обоих постоянное, когда достигается точка встречи.
Таким образом, используя простое соотношение скорости, времени и расстояния 2 (x + y) = x + 2y + z => x + 2y + z = 2x + 2y => x = z
Следовательно, перемещая slowPointer в начало связанного списка и заставляя slowPointer и fastPointer перемещать один узел за раз, они оба имеют одинаковое расстояние для покрытия .
Они достигнут точки, где цикл начинается в связанном списке.
источник
Простой и недооцененный ответ старого монаха объясняет нахождение цикла, когда быстрый бегун завершает только один полный цикл. В этом ответе я объясняю случай, когда быстрый бегун запускает цикл несколько раз, прежде чем медленный бегун входит в цикл.
Используя то же изображение:
Допустим, быстрый бегун выполнил цикл m раз, прежде чем встретиться медленно и быстро. Это означает, что:
Поскольку быстрые пробеги с удвоенной скоростью замедления и то, что они бегали в одно и то же время, это означает, что если мы удвоим расстояние, пройденное медленным, мы получим расстояние, пройденное быстро Таким образом,
Решение для х дает,
В реальном сценарии это будет означать, что x = (m - 1) полный цикл проходит + дополнительное расстояние z .
Следовательно, если мы поместим один указатель в начало списка, а другой оставим в точке встречи, то перемещение их с той же скоростью приведет к тому, что указатель в цикле завершит m - 1 циклов цикла, а затем встретит другой указатель прямо в начале цикла.
источник
Это очень очень просто. Вы можете думать с точки зрения относительной скорости. Если кролик перемещается на два узла, а черепаха перемещается на один узел, то по отношению к черепахе кролик перемещается на один узел (предположим, черепаха в покое). Итак, если мы переместим один узел в круговом связанном списке, мы обязательно встретимся в этот момент снова.
После нахождения связанной точки в круговом связанном списке теперь проблема сводится к поиску точки пересечения задачи двух связанных списков.
источник
Во время первого столкновения черепаха переместилась на m + k шагов, как показано выше. Заяц движется в два раза быстрее черепахи, то есть заяц прошел 2 (m + k) шага. Из этих простых фактов мы можем вывести следующий график.
В этот момент мы возвращаем черепаху к началу и заявляем, что и заяц, и черепаха должны двигаться по одному шагу за раз. По определению, после m шагов черепаха будет в начале цикла. Где зайца будет?
Заяц также будет в начале цикла. Это видно из второго графика: когда черепаха была возвращена к началу, займ был на k шагов в свой последний цикл. После m шагов заяц завершит еще один цикл и столкнется с черепахой.
источник
Подходить:
Есть два указателя:
Если два указателя встречаются, это доказывает, что есть цикл. После того, как они встретились, один из узлов будет указывать на голову, а затем оба будут проходить по одному узлу за раз. Они встретятся в начале цикла.
Обоснование: Когда два человека идут по круговой дорожке, один из них с удвоенной скоростью, другой, где они встречаются? Именно там, где они начали.
Теперь предположим, что быстрый бегун имеет быстрый старт
k
шагов наn
круге. где они встретятся? Именно наn-k
шагах. Когда медленный бегун покрыл(n-k)
шаги, быстрый бегун покрыл быk+2(n-k)
шаги. ( то естьk+2n-2k
шаги, то есть2n-k
шаги ). т.е.(n-k)
шаги (путь круговой, и нас не волнует количество раундов, после которых они встречаются; нас просто интересует положение, где они встречаются).Теперь, как быстрый бегун получил быстрый старт
k
шагов во-первых? Потому что медленному бегуну понадобилось столько шагов, чтобы достичь начала цикла. Таким образом, начало цикла составляет k шагов от головного узла.Примечание . Узел, где встречаются оба указателя, находится в нескольких
k
шагах от начала цикла (внутри цикла), а головной узел также находится в несколькихk
шагах от начала цикла. Поэтому, когда у нас есть движение указателя с одинаковым шагом в 1 шаг от бота, эти узлы встретятся в начале цикла.Я считаю, что это просто. Пожалуйста, дайте мне знать, если какая-то часть неоднозначна.
источник
Итак, давайте предположим, что заяц и черепаха встречаются в точке, которая находится в k шагах от начала цикла, число шагов до начала цикла равно мю, а длина цикла равна L.
Так что теперь на месте встречи ->
Расстояние, пройденное черепахой = mu + a * L + k - Уравнение 1
(Шаги, предпринятые для достижения начала цикла + шаги, предпринятые для охвата «и» итераций цикла + k шагов от начала цикла) (где a - некоторая положительная постоянная)
Расстояние, пройденное зайцем = mu + b * L + k - уравнение 2
(Шаги, предпринятые для достижения начала цикла + шаги, предпринятые для охвата «b» итераций цикла + k шагов от начала цикла) (где b - некоторая положительная постоянная, а b> = a)
Таким образом, дополнительное расстояние, пройденное зайцем, составляет = Уравнение 2 - Уравнение 1 = (ba) * L
Обратите внимание, что это расстояние также равно расстоянию черепахи от начальной точки, поскольку заяц движется в 2 раза быстрее, чем черепаха. Это может быть приравнено к 'mu + k', которое также является расстоянием до точки встречи от начала, если мы не включаем многократные обходы цикла.
Таким образом, mu + k = (ba) * L
Таким образом, некоторые шаги с этой точки могут привести к началу цикла (поскольку k шагов от начала цикла уже были предприняты для достижения точки встречи). Это может произойти в том же цикле или любом из последующих циклов. Таким образом, теперь, если мы переместим черепаху в начало связанного списка, потребуется несколько шагов, чтобы достичь начальной точки цикла, а заяц предпримет несколько шагов, чтобы также достичь начала цикла, и, таким образом, они оба встретятся в отправная точка цикла.
PS Честно говоря, у меня был тот же вопрос, что и у оригинального плаката, и я прочитал первый ответ, они кое-что прояснили, но я не смог четко получить конечный результат, поэтому я попытался сделать это по-своему и легче понять.
источник
кредит изображения
Вызовите расстояние - количество ссылок, за которыми следует указатель, и время, которое занимает алгоритм для перемещения медленного указателя на одну ссылку и быстрого указателя на две ссылки. Перед циклом длиной C имеется N узлов, помеченных смещением цикла от k = 0 до C-1.
Чтобы достичь начала цикла, медленный занимает N времени и расстояния. Это означает, что быстро занимает N расстояние в цикле (N, чтобы добраться, N, чтобы вращаться). Таким образом, в момент времени N медленное значение равно смещению цикла k = 0, а быстрое значение равно смещению цикла k = N mod C.
Если N mod C равно нулю, медленные и быстрые теперь совпадают, и цикл находится в момент времени N и позиция цикла k = 0.
Если N mod C не равно нулю, тогда fast теперь должен догнать медленный, который в момент N является C- (N mod C) расстоянием позади в цикле.
Поскольку быстрые перемещения 2 для каждого 1 медленного, сокращая расстояние на 1 на каждой итерации, это занимает столько же дополнительного времени, сколько расстояние между быстрым и медленным в момент N, который равен C- (N mod C). Поскольку замедление движется от смещения 0, это также смещение, где они встречаются.
Таким образом, если N mod C равно нулю, фаза 1 останавливается после N итераций в начале цикла. В противном случае фаза 1 останавливается после итераций N + C- (N mod C) со смещением C- (N mod C) в цикл.
Итак, фаза 2: замедление занимает еще N шагов, чтобы добраться до цикла, и в этот момент быстрое (теперь перемещается 1 за шаг) находится в (C- (N mod C) + N) mod C = 0. Таким образом, они встречаются в начале цикла после фазы 2.
Для полноты, фаза 3 вычисляет длину цикла, продвигаясь еще раз через цикл:
источник
Сведите проблему к проблеме цикла, затем вернитесь к исходной проблеме.
Я считаю следующее объяснение более интуитивным.
Возьмите два указателя ( 1 = черепаха и 2 = заяц), которые начинаются с головы ( O ), 1 имеет длину шага 1 , 2 имеет длину шага 2 . Подумайте о том моменте, когда 1 достигает начального узла этого цикла ( A ).
Мы хотим ответить на следующий вопрос: «Где 2, когда 1 в A?» ,
Итак,
OA = a
натуральное число (a >= 0
). Но это можно записать следующим образом:,a = k*n + b
гдеa, k, n, b are natural numbers
:n
= длина циклаk >= 0
= постоянная0 <= b <= n-1
Это значит что
b = a % n
.Например: если
a = 20
иn = 8
=>k = 2
иb = 4
потому что20 = 2*8 + 4
.Расстояние, пройденное на 1 есть
d = OA = a = k*n + b
. Но в то же время 2 обложкиD = 2*d = d + d = OA + d = OA + k*n + b
. Это означает, что когда 2 находится в A, оно должно покрыватьk*n + b
. Как вы можете видеть,k
это число кругов, но после этих кругов 2 будет b далеко от A. Итак, мы нашли, где 2 - это когда 1 находится в A. Давайте назовем ту точкуB
, гдеAB = b
.Теперь мы сводим задачу к кругу. Вопрос "Где место встречи?" , Где это С ?
На каждом шаге 2 уменьшает расстояние от 1 с
1
(скажем, метр), потому что 1 продвигается дальше от 2 с1
, но в то же время 2 приближается к 1 на2
.Таким образом, пересечение будет, когда расстояние между 1 и 2 будет равно нулю. Это означает, что 2 уменьшает
n - b
расстояние. Для этого 1 сделаетn - b
шаги, а 2 сделает2*(n - b)
шаги.Таким образом, точка пересечения будет находиться
n - b
далеко от A (по часовой стрелке), потому что это расстояние, пройденное 1, пока не встретит 2 . => расстояние между C и A естьCA = b
, потому чтоAC = AB + BC = n - b
иCA = n - AC
. Не думайте, чтоAC = CA
, посколькуAC
расстояние не является тривиальным математическим расстоянием, это число шагов между A и C (где A - начальная точка, а C - конечная точка).Теперь вернемся к исходной схеме.
Мы знаем это
a = k*n + b
иCA = b
.Мы можем взять 2 новых указателя 1 ' и 1' ' , где 1' начинается с головы ( O ), а 1 '' начинается с точки пересечения ( C ).
В то время как 1 ' идет от О до А , 1' ' идет от С до А и продолжает заканчивать
k
круги. Таким образом, точка пересечения .источник
Если указатели встречаются в точке P, как показано на рисунке, расстояние Z + Y является точкой P, а X + Y также является точкой P, что означает Z = X. Вот почему продолжайте перемещать один указатель из P и перемещать другой от начала (S) до их встречи, что означает перемещение на одинаковое расстояние (Z или X) к той же точке M (расстояние Z от P и X от S) будет начало цикла. Просто!
источник
С учетом всего вышеприведенного анализа, если вы учитесь на личном опыте, я попытался написать краткий анализ и пример, который поможет объяснить математику, которую пытались объяснить все остальные. Вот так!
Анализ:
Если у нас есть два указателя, один быстрее другого, и они движутся вместе, они в конечном итоге встретятся снова, чтобы указать цикл или ноль, чтобы указать отсутствие цикла.
Чтобы найти начальную точку цикла, позвольте ...
m
расстояние от головы до начала цикла;d
быть числом узлов в цикле;p1
скорость медленного указателя;p2
быть скоростью более быстрого указателя, например. 2 означает шаги через два узла одновременно.Соблюдайте следующие итерации:
Из приведенных выше примеров данных мы можем легко обнаружить, что всякий раз, когда более быстрые и медленные указатели встречаются, они находятся в нескольких
m
шагах от начала цикла. Чтобы решить эту проблему, поместите более быстрый указатель обратно в головку и установите его скорость равной скорости более медленного указателя. Когда они встречаются снова, узел является началом цикла.источник
скажем так,
у нас есть 2 указателя A и B, A работает с 1-кратной скоростью, B с 2-кратной скоростью, оба начинаются с начала.
когда A достигает N [0], B уже должен быть в N [m]. (Примечание: A использует m шагов для достижения N [0], а B должно быть m шагов дальше)
Затем A выполняет еще k шагов, чтобы столкнуться с B, т. Е. A находится в N [k], B находится в N [m + 2k] (Примечание: B должно пройти 2k шагов, начиная с N [m])
Столкновение B в N [k] и N [m + 2k] соответственно означает k = m + 2k, следовательно, k = -m
Таким образом, чтобы вернуться к N [0] из N [k], нам нужно еще m шагов.
Проще говоря, нам нужно выполнить еще m шагов после того, как мы нашли узел столкновения. У нас может быть указатель для запуска с начала и указатель от узла столкновения, они встретятся в N [0] после m шагов.
Следовательно, псевдокод выглядит следующим образом:
источник
Я не думаю, что это правда, что когда они встречаются, это отправная точка. Но да, если другой указатель (F) был в точке встречи раньше, чем этот указатель будет в конце цикла вместо начала цикла и указатель (S), который начался с начала списка, будет в конечном итоге в начале цикла. например:
источник
Простое объяснение с использованием идеи относительной скорости, преподаваемой в старшей школе, - физика 101 / Кинематика лекций.
Предположим, расстояние от начала связанного списка до начала круга равно
x
прыжкам. Назовем начало круга точкойX
(в заглавных буквах - см. Рисунок выше). Также предположим, что общий размер круга составляет N прыжков.Скорость зайца = 2 * Скорость черепахи. Так что есть
1 hops/sec
и2 hops/sec
соответственноКогда черепаха достигает начала круга
X
, заяц долженx
прыгать дальше в точкеY
на рисунке. (Потому что заяц преодолел вдвое большее расстояние, чем черепаха).Таким образом, длина оставшейся дуги по часовой стрелке от X до Y будет
N-x
. Это также оказывается относительным расстоянием, которое должно быть пройдено между зайцем и черепахой, чтобы они могли встретиться . Допустим, это относительное расстояние будет пройдено во времени,t_m
т.е. во времени встречи. Относительная скорость(2 hops/sec - 1 hops/sec)
есть1 hops/sec
. Таким образом, используя, относительное расстояние = относительная скорость X время, мы получаем,t
=N-x
сек. Так что потребуется,N-x
чтобы добраться до места встречи черепахи и зайца.Теперь через
N-x
секунду и со1 hops/sec
скоростью черепаха, которая была ранее в точке,X
будет покрывать Nx прыжков, чтобы достичь места встречиM
. Таким образом, это означает, что точка встречиM
находится вN-x
прыжках против часовой стрелки отX
= (что также подразумевает) => что естьx
расстояние, оставшееся от точкиM
до поX
часовой стрелке.Но
x
это также расстояние до точки достиженияX
от начала связанного списка.Теперь нас не волнует, какое количество прыжков
x
соответствует. Если мы поместим одну черепаху в начале LinkedList и одну черепаху в место встречиM
и позволим им прыгать / ходить, тогда они встретятся в точкеX
, которая является точкой (или узлом), которая нам нужна.источник
Работа с диаграммой поможет. Я пытаюсь объяснить проблему без уравнений.
источник
Есть k шагов до цикла. Мы не знаем, что такое k, и нам не нужно это выяснять. Мы можем работать абстрактно только с k.
- после k шагов
----- T в начале цикла
----- H это k шагов в цикле (он пошел 2k всего и, таким образом, k в цикл)
** они теперь петлеобразные - к друг от друга
(обратите внимание, что k == K == mod (loopsize, k) - например, если узел проходит 2 шага в цикле из 5 узлов, он также включает 7, 12 или 392 шага, поэтому, насколько велик цикл по отношению к k, не имеет значения фактор в.
Так как они догоняют друг друга со скоростью 1 шаг в единицу времени, потому что один движется в два раза быстрее другого, они встретятся с размером петли - k.
Это означает, что потребуется k узлов, чтобы достичь начала цикла, и, таким образом, расстояние от начала до начала цикла и столкновения до начала цикла одинаковы.
Так что теперь после первого столкновения верните Т обратно в голову. T и H встретятся при старте, если вы двигаетесь со скоростью 1 каждый. (по k шагов для обоих)
Это означает, что алгоритм:
// заботиться о случае, когда k = 0 или T и H встретились в начале цикла, вычисляя длину цикла
- рассчитать длину цикла, перемещая T или H вокруг него с помощью счетчика
- переместить указатель T2 в начало списка
- указатель длины цикла шагов
- переместить другой указатель H2 на голову
- перемещать Т2 и Н2 в тандеме, пока они не встретятся в начале цикла
Это оно!
источник
На это уже есть множество ответов, но однажды я придумал диаграмму для этого, которая является более наглядной для меня. Возможно, это может помочь другим людям.
Основными аха-моментами для меня были:
Разделите T (черепаха) на T1 (предварительный цикл) и T2 (внутри цикл).
Вычтите T из H , где они визуально перекрываются. То , что остается ( H - T = H» ) равна Т .
источник
Я знаю, что уже есть принятый ответ на эту проблему, но я все еще попытаюсь ответить в жидкой форме. Предполагать :
Теперь, пусть заяц и черепаха встретятся через время «т» от начала.
Замечания:
Если расстояние, пройденное черепахой = v * t = x + (bk) (скажем)
Затем расстояние, пройденное зайцем = 2 * v * t = x + (b - k) + b (поскольку заяц уже однажды прошел по зацикленной части)
Время встреч там одинаковое.
=> x + 2 * b - k = 2 * (x + b - k)
=> х = к
Это, конечно, означает, что длина пути, который не является зацикленным, равна расстоянию начальной точки цикла от точки, где встречаются оба.
источник
На самом деле легко доказать, что они оба встретятся в начальной точке, если вы рассмотрите математику за точкой встречи.
Во-первых, пусть m обозначает начальную точку цикла в связанном списке, а n обозначает длину цикла. Тогда для зайца и черепахи встретиться имеем:
Заявив это более математически:
поэтому они встретятся в момент времени t, который должен быть кратным длине цикла. Это означает, что они встречаются в месте, которое есть
(t-m) modulo n = (0-m) modulo n = (-m) modulo n
.Итак, теперь возвращаясь к вопросу, если вы переместите один указатель из начала связанного списка, а другой из точки пересечения, после m шагов мы получим, что заяц (который движется внутри цикла) придет к точке, которая
((-m) + m) modulo n = 0 modulo n
которая является ничем иным, как начальной точкой цикла. Итак, мы можем видеть, что после m шагов наступает начало цикла, и черепаха встретит его там, поскольку будет проходить m шагов от начала связанного списка.В качестве примечания, мы также можем рассчитать время их пересечения следующим образом: Условие
t = 0 modulo n
говорит нам, что они встретятся за время, кратное длине цикла, а также t должно быть больше, чем m, как они встретились бы в цикл . Таким образом, время будет равно первому кратному n, которое больше m .источник
Предположим, что ваши указатели встречаются на пересечении точек y и z.
n и m числа циклов быстрее и медленнее указатель занимает соответственно до встречи.
Обратитесь к изображению для остальной части доказательства. Найти начальную точку цикла в связанном списке
источник