Объясните, как работает узел запуска цикла в циклическом списке?

Я понимаю, что встреча в черепахе и Харе завершает существование цикла, но как перемещение черепахи до начала связанного списка, удерживая зайца на месте встречи, а затем перемещая оба шага за один раз, они встречаются в начальной точке цикла?

Это алгоритм Флойда для обнаружения циклов . Вы спрашиваете о втором этапе алгоритма – как только вы нашли узел, который является частью цикла, как найти начало цикла?

В первой части алгоритма Флойда заяц перемещается на два шага для каждого шага черепахи. Если черепаха и заяц когда-либо встречаются, существует цикл, и точка встречи является частью цикла, но не обязательно первым узлом цикла.

Когда черепаха и зайчик встречаются, мы нашли наименьшее i (количество шагов, сделанных черепахой), так что X i = X 2i . Пусть mu представляет число шагов для перехода от X 0 к началу цикла и пусть lambda представляет длину цикла. Тогда i = mu + a lambda и 2i = mu + b lambda, где a и b являются целыми числами, обозначающими, сколько раз черепаха и зайц обошли цикл. Вычитание первого уравнения из второго дает i = (ba) * lambda, поэтому i является целым числом, кратным lambda. Следовательно, X i + mu = X mu . X i представляет собой место встречи черепахи и зайца. Если вы переместите черепаху обратно в исходный узел X 0 , и пусть черепаха и зайчик продолжат с той же скоростью, после дополнительных шагов черепаха достигнет X mu , а заяц достигнет X i + mu = X mu , поэтому вторая точка встречи обозначает начало цикла.

Позвольте мне попытаться прояснить алгоритм обнаружения цикла, который предоставляется по адресу http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare своими собственными словами.

Я ссылаюсь на цифру Рисование в моем объяснении.

Как это работает

Давайте иметь черепаху и зайца (имя указателей), указывающих на начало списка с циклом.

Давайте предположим, что если мы будем перемещать черепаху на 1 шаг за раз и заячьте 2 шага за раз, они в конечном итоге будут встречаться в определенной точке. Покажем, что в первую очередь эта гипотеза верна.

На рисунке показан список с циклом. Цикл имеет длину n и мы изначально находимся в шаге от цикла. Также предположим, что точка встречи находится в шагах от начала цикла, а черепаха и заяц встречаются после всех шагов.

Должны соблюдаться следующие 2 условия:

 1) i = m + p * n + k 2) 2i = m + q * n + k 

Первый говорит, что черепаха движется по ступенькам, и в этих шагах он сначала добирается до цикла. Затем он проходит цикл p раз для некоторого положительного числа p . Наконец, он перебирает больше узлов, пока не встретится с зайцем.

Аналогично для зайца. Он перемещается на 2 шага и на этих 2-х шагах сначала переходит к циклу. Затем он проходит цикл q раз для некоторого положительного числа q . Наконец, он перебирает больше узлов, пока не встретит черепаху.

Как заяц путешествует с удвоенной скоростью черепахи, и время остается постоянным, когда они достигают места встречи.

Таким образом, используя простую скорость, соотношение времени и расстояния,

 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 = mn - m 

Мы можем проверить, что эти значения работают следующим образом:

 m + k = ( q - 2p ) n => m + mn - m = ( m - 2*0) n => mn = mn. 

Для этого множества i

 i = m + pn + k => m + 0 * n + mn - m = mn. 

Конечно, вы должны убедиться, что это не обязательно самый маленький. Другими словами, черепаха и заяц, возможно, уже встречались много раз. Однако, поскольку мы показываем, что они встречаются в какой-то момент, по крайней мере, как только мы можем сказать, что гипотеза верна. Поэтому они должны были бы встретиться, если мы переместим один из них на один шаг, а второй – на 2 шага за раз.

Теперь мы можем перейти ко второй части алгоритма, которая заключается в том, как найти начало цикла.

Начало цикла

Как только черепаха и зайчик встречаются, давайте вернем черепаху к началу списка и держим зайца там, где они встретились (что находится в шагах от начала цикла).

Гипотеза состоит в том, что, если мы позволяем им двигаться с одинаковой скоростью (1 шаг для обоих), первый раз, когда они когда-либо встречаются снова, будет начало цикла.

Докажем эту гипотезу.

Давайте сначала предположим, что какой-то oracle говорит нам, что такое m.

Затем, если мы позволяем им перемещать шаги m + k, черепаха должна была бы достичь точки, которую они встречали первоначально (в шагах от начала цикла – см. Рисунок).

Ранее мы показали, что m + k = (q - 2p) n .

Так как m + k шагов кратно длине цикла n, заяц, в среднем время, будет проходить цикл (q-2p) раз и возвратится в ту же точку (в шагах от начала цикла).

Теперь вместо того, чтобы позволить им перемещать m + k шагов, если мы позволяем им перемещаться только на m шагов, черепаха придет к началу цикла. Заяц остался бы на k шагов до завершения (q-2p) вращений. Так как он начал k шагов перед началом цикла, заяц должен был прийти к началу цикла.

В результате это объясняет, что они должны были встретиться в начале цикла после некоторого количества шагов в первый раз (очень первый раз, потому что черепаха только что достигла цикла после m шагов, и он никогда не мог видеть зайца, который уже был в цикл).

Теперь мы знаем, что количество шагов, необходимых для их перемещения до их соответствия, оказывается расстоянием от начала списка до начала цикла, т. Конечно, алгоритм не должен знать, что такое m. Он будет просто перемещать черепаху и зайца на один шаг за один раз, пока они не соберутся. Местом встречи должно быть начало цикла, а число шагов должно быть расстоянием (m) до начала цикла. Предполагая, что мы знаем длину списка, мы также можем вычислить длину цикла вычитания m из длины списка.

См. Это изображение:

введите описание изображения здесь

Расстояние, пройденное 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 + y
  • Расстояние выполняется быстрым: x + m (y + z) + y, т.е. дополнительно y, где они встречаются

Так как быстрые пробеги с удвоенной скоростью медленны и что они работают в одно и то же время, это означает, что если мы удвоим расстояние, пройденное медленным, мы получим расстояние, быстро пройденное. Таким образом,

  • 2 (x + y) = x + m (y + z) + y

Решение для x дает,

x = (m – 1) (y + z) + z

В реальном сценарии это означало бы, что x = (m – 1) полный цикл пробега + дополнительное расстояние z .

Следовательно, если мы помещаем один указатель в начало списка и оставляем другого в точке встречи, то перемещение их с той же скоростью приведет к тому, что указатель цикла цикла завершит m-1 прогонов цикла, а затем встретит другой указатель прямо в начале цикла.

Рисунок 1

Во время первого столкновения черепаха перемещала m + k шагов, как показано выше. Заяц перемещается в два раза быстрее, чем черепаха, т. Е. Заяц перемещается на 2 (м + к) шага. Из этих простых фактов можно получить следующий граф.

Рисунок 1

На этом этапе мы перемещаем черепаху обратно к началу и заявляем, что и заяц, и черепаха должны двигаться один шаг за раз. По определению, после m шагов черепаха будет в начале цикла. Где будет зайцем?

Заяц также будет в начале цикла. Это видно из второго графика: когда черепаха была перенесена обратно в начало, заяц был k шагов в последний цикл. После m шагов, заяц завершит еще один цикл и столкнется с черепахой.

Итак, давайте предположим, что заяц и черепаха встречаются в точке, которая находится в шагах от начала цикла, количество шагов до начала цикла – mu, а длина цикла равна 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

Таким образом, шаги mu от этого момента вернутся к началу цикла (так как k шагов с начала цикла уже были приняты для достижения точки встречи). Это может произойти в том же цикле или в любом из последующих циклов. Таким образом, теперь, если мы переместим черепаху в начало связанного списка, для достижения начальной точки цикла потребуются шаги mu, и заяц предпримет шаги mu, чтобы достичь начала цикла, и поэтому они оба будут встречаться на отправной точкой цикла.

PS Честно говоря, у меня был тот же вопрос, что и исходный плакат, и я прочитал первый ответ, они прояснили несколько вещей, но я не смог четко понять окончательный результат, поэтому я попытался сделать это по-своему и было легче понять.

Это очень просто. Вы можете думать с точки зрения относительной скорости. Если кролик перемещает два узла, а черепаха перемещается на один узел, по отношению к черепаховому кролику движется один узел (возьмите черепаху в покое). Итак, если мы переместим один узел в круговом связанном списке, мы обязательно встретимся в этом месте снова.

После нахождения связанной точки внутри кругового связанного списка, теперь проблема сводится к нахождению точки пересечения проблемы с двумя связанными списками.

Подход:

Есть два указателя:

  • Медленный указатель, который перемещает один узел за раз.
  • Быстрый указатель, который перемещает два узла за раз.

Если два указателя встречаются, это доказывает, что существует петля. Как только они сработают, один из узлов укажет на голову, а затем оба будут двигаться по одному узлу за раз. Они будут встречаться в начале цикла.

Обоснование: когда двое людей идут по круговой дорожке, одна из них в два раза быстрее другой, где они встречаются? Именно там, где они начались.

Теперь предположим, что у быстрого бегуна начальный шаг k шагов на n шаге. где они будут встречаться? Именно на nk шагах. Когда медленный бегун покрыл шаги (nk) , быстрый бегун занял бы шаги k+2(nk) . ( т. е. k+2n-2k шагов, т.е. 2n-k шагов ). т.е. (nk) шагов (путь круглый, и нас не волнует количество раундов, после которых они встречаются, нас просто интересует положение, в котором они встречаются).

Теперь, как быстрый бегун получил начальное начало k шагов в первую очередь? Потому что для медленного бегуна потребовалось много шагов, чтобы достичь начала цикла. Таким образом, начало цикла составляет k шагов от головного узла.

Примечание . Узел, где оба указателя совпадают, находится в шаге от начала цикла (внутри цикла), а головной узел также находится в шаге от начала цикла. Поэтому, когда у нас есть указатель, продвигающийся в равном темпе на 1 шаг от бота этих узлов, они будут встречаться в начале цикла.

Я считаю, что это просто. Пожалуйста, дайте мне знать, если какая-либо часть неоднозначна.

Уменьшите проблему до проблемы цикла, затем вернитесь к исходной задаче

Я нахожу следующее объяснение более интуитивным.

  1. Возьмите два указателя ( 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 будет далек от A. Итак, мы обнаружили, где 2 , когда 1 находится в A. Назовем эту точку B , где AB = b .

    введите описание изображения здесь

  2. Теперь мы сводим задачу к кругу. Вопрос: «Где место встречи?» , Где это C ?

    введите описание изображения здесь

    На каждом шаге 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 - конечная точка).

  3. Теперь вернемся к исходной схеме.

    Мы знаем, что a = k*n + b и CA = b .

    Мы можем взять 2 новых указателя 1 ' и 1' ' , где 1' начинается с головы ( O ), а 1 '' начинается с точки пересечения ( C ).

    В то время как 1 ' идет от O до A , 1' ' переходит от C в A и продолжает заканчивать k кругов. Таким образом, точка пересечения равна A.

    введите описание изображения здесь

    введите описание изображения здесь

На самом деле легко доказать, что оба они будут встречаться в начальной точке, если вы рассмотрите математику за местом встречи.
Сначала пусть m обозначает начальную точку цикла в связанном списке, а n обозначает длину цикла. Тогда для зайца и черепахи встретиться, мы имеем:

 ( 2*t - m )%n = (t - m) %n, where t = time (at t = 0 , both are at the start) 

Сформулируйте это более математически:

 (2*t - m - (t - m) ) = 0 modulo n , which implies , t = 0 modulo n 

поэтому они будут встречаться в момент времени t, который должен быть кратным длине цикла. Это означает, что они встречаются в месте, которое (tm) 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 .

Со всем рассмотренным выше анализом, если вы являетесь учеником по отдельности, я попытался написать короткий анализ и пример, который поможет объяснить математику, которую все остальные пытались объяснить. Вот так!

Анализ:

Если у нас есть два указателя, один быстрее, чем другой, и перемещайте их вместе, они в конце концов снова соберутся, чтобы указать цикл или нуль, чтобы не указывать никакого цикла.

Чтобы найти начальную точку цикла, позвольте …

  1. m – расстояние от головы до начала цикла;
  2. d – количество узлов в цикле;
  3. p1 – скорость медленного указателя;
  4. p2 – скорость более быстрого указателя, например. 2 означает шаги по двум узлам за раз.

    Соблюдайте следующие итерации:

  m = 0, d = 10: p1 = 1: 0 1 2 3 4 5 6 7 8 9 10 // 0 would the start of the cycle p2 = 2: 0 2 4 6 8 10 12 14 16 18 20 m = 1, d = 10: p1 = 1: -1 0 1 2 3 4 5 6 7 8 9 p2 = 2: -1 1 3 5 7 9 11 13 15 17 19 m = 2, d = 10: p1 = 1: -2 -1 0 1 2 3 4 5 6 7 8 p2 = 2: -2 0 2 4 6 8 10 12 14 16 18 

Из приведенных выше выборочных данных мы можем легко обнаружить, что всякий раз, когда встречаются более быстрые и медленные указатели, они находятся в нескольких шагах от начала цикла. Чтобы решить эту проблему, верните указатель быстрее на голову и установите скорость на скорость более медленного указателя. Когда они снова встречаются, узел является началом цикла.

скажем,

 N[0] is the node of start of the loop, m is the number of steps from beginning to N[0]. 

у нас есть 2 указателя A и B, A работает со скоростью 1x, B с 2x скоростью, оба начинаются с начала.

когда 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])

Колладиум В при N [k] и N [m + 2k] соответственно, это означает k = m + 2k, таким образом, k = -m

Таким образом, чтобы вернуться к N [0] из N [k], нам понадобится еще несколько шагов.

Просто говоря, нам просто нужно выполнить еще несколько шагов после того, как мы нашли узел столкновения. У нас может быть указатель на запуск с начала и указатель, запущенный из узла столкновений, они будут встречаться при N [0] после m шагов.

Поэтому псевдокод выглядит следующим образом:

 1) A increase 1 step per loop 2) B increase 2 steps per loop 3) if A & B are the same node, cycle found, then go to 5 4) repeat from 1 5) A reset to head 6) A increase 1 step per loop 7) B increase 1 step per loop 8) if A & B are the same node, start of the cycle found 9) repeat from 6 

Я не думаю, что это правда, что, когда они встречают это, отправная точка. Но да, если другой указатель (F) находился на месте встречи раньше, чем этот указатель будет в конце цикла вместо начала цикла и указателя (S), который начался с начала списка, он будет заканчивается в начале цикла. например:

 1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18->19->20->21->22->23->24->8 Meet at :16 Start at :8 public Node meetNodeInLoop(){ Node fast=head; Node slow=head; fast=fast.next.next; slow=slow.next; while(fast!=slow){ fast=fast.next; fast=fast.next; if(fast==slow) break; slow=slow.next; } return fast; } public Node startOfLoop(Node meet){ Node slow=head; Node fast=meet; while(slow!=fast){ fast=fast.next; if(slow==fast.next) break; slow=slow.next; } return slow; } в 1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18->19->20->21->22->23->24->8 Meet at :16 Start at :8 public Node meetNodeInLoop(){ Node fast=head; Node slow=head; fast=fast.next.next; slow=slow.next; while(fast!=slow){ fast=fast.next; fast=fast.next; if(fast==slow) break; slow=slow.next; } return fast; } public Node startOfLoop(Node meet){ Node slow=head; Node fast=meet; while(slow!=fast){ fast=fast.next; if(slow==fast.next) break; slow=slow.next; } return slow; } в 1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18->19->20->21->22->23->24->8 Meet at :16 Start at :8 public Node meetNodeInLoop(){ Node fast=head; Node slow=head; fast=fast.next.next; slow=slow.next; while(fast!=slow){ fast=fast.next; fast=fast.next; if(fast==slow) break; slow=slow.next; } return fast; } public Node startOfLoop(Node meet){ Node slow=head; Node fast=meet; while(slow!=fast){ fast=fast.next; if(slow==fast.next) break; slow=slow.next; } return slow; } 

Простое объяснение с использованием идеи относительной скорости, преподаваемой в средней школе – Physics 101 / Kinematics.

Круг в LinkedList

  1. Предположим, что расстояние от начала связанного списка до начала круга – x хеп. Назовем начало круга как точку X (в шапках – см. Рисунок выше). Также предположим, что общий размер круга – это N прыжков.

  2. Скорость зайца = 2 * Скорость черепахи. Итак, это 1 hops/sec и 2 hops/sec соответственно

  3. Когда черепаха достигает начала круга X , заяц должен далее x хлынуть в точке Y на рисунке. (Потому что заяц проехал вдвое больше, чем черепаха).

  4. Таким образом, длина оставшейся дуги по часовой стрелке от X до Y будет равна Nx . Т его также оказывается относительным расстоянием между зайцем и черепахой, чтобы они могли встретиться . Предположим, что это относительное расстояние будет покрываться за время t_m т.е. время для встречи. Относительная скорость (2 hops/sec - 1 hops/sec) т.е. 1 hops/sec . Таким образом, используя относительное расстояние = относительная скорость X времени, получаем t = Nx сек. Таким образом, Nx достигнет места встречи как для черепахи, так и для зайца.

  5. Теперь, в течение Nx сек и со скоростью 1 hops/sec , черепаха, которая раньше находилась в точке X будет покрывать Nx-прыжки, чтобы добраться до места встречи M Таким образом, это означает, что точка встречи M находится в Nx прыжках против часовой стрелки от X = (что дополнительно подразумевает) =>, что есть расстояние x оставшееся от точки M до X часовой стрелке.

  6. Но x также является расстоянием до точки X с начала связанного списка.

  7. Теперь нам все равно, какое число x соответствует. Если мы ставим одну черепаху в начале LinkedList и одну черепаху в точке встречи M и позволяем им прыгать / ходить, то они будут встречаться в точке X , которая является точкой (или узлом), которая нам нужна.

Работа с диаграммой поможет. Я пытаюсь объяснить проблему без уравнений.

  1. Если мы позволяем зайцу и черепахе бегать по кругу, а заяц бежит два раза черепаха, то в конце одного круга для зайца черепаха будет в два раза. В конце двух кругов от зайца-черепахи было бы сделано 1 круг, и они оба встретились. Это относится ко всей скорости, как если бы заяц работал три раза, заяц 1 круга равнялся 1/3 черепахи, поэтому в конце 3 круга для зайца-черепахи покрыл бы 1 круг и они встретились.
  2. Теперь, если мы начнем их m шагов до цикла, тогда это означает, что более быстрый заяц начинает движение вперед в цикле. Так что, если черепаха достигнет начала цикла, заяц будет m шагов вперед, и когда они будут соответствовать, это будет m шагов до начала цикла.

В большинстве решений для этой проблемы есть ошибка. Что, если последний узел был связан с первым, и это был просто цикл? Что делать, если медленно и быстро встретились во главе цикла в первый раз? Вы не нашли бы правильного ответа с этим решением. Существует правильный ответ о том, как вы избегаете этой ситуации, но, учитывая счастливый путь, с несколькими узлами k перед циклом, вот простое объяснение: (если вы хотите узнать больше о реальном обобщенном решении, пинге меня)

– перед циклом есть k шагов. Мы не знаем, что такое k, и не нужно выяснять. Мы можем работать абстрактно с помощью k.

– После k шагов

—– T находится в начале цикла

—– H – k шагов в цикл (он пошел 2k всего и, таким образом, k в цикл)

** теперь они изогнуты – k друг от друга

(обратите внимание, что k == K == mod (loopsize, k) –eg, если узел равен 2 шагам в 5-узловой цикл, это также 7, 12 или 392 шага, поэтому, насколько большой цикл равен k, не фактор в.

Так как они догоняют друг друга со скоростью 1 шаг за единицу времени, потому что один движется в два раза быстрее, чем другой, они будут встречаться при loopsize-k.

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

Итак, теперь, после первого столкновения, двигайтесь обратно к голове. T и H будут встречаться на велосипеде, если вы будете двигаться со скоростью 1 каждый. (в k шагов для обоих)

Это означает, что алгоритм:

  • от перемещения головы T = t.next и H.next.next до тех пор, пока они не столкнутся (T == H) (есть цикл)

// позаботимся о случае, когда k = 0 или T и H встретились в начале цикла, вычислив длину цикла

– указать длину цикла, перемещая T или H вокруг него с помощью счетчика

– переместите указатель T2 в начало списка

– увеличить длину указателя цикла

– переместить другой указатель H2 в голову

– перемещать T2 и H2 в тандеме, пока они не встречаются в начале цикла

это оно!

введите описание изображения здесь

Если указатели встречались в точке P, как показано на рисунке, расстояние Z + Y является точкой P, а X + Y также является точкой P, что означает Z = X. Поэтому удерживание перемещения одного указателя из P и перемещение другого из начала (S) до их соответствия, что означает перемещение равного расстояния (Z или X) в ту же точку M (расстояние Z от P и X от S) будет начало цикла. Просто!

Я знаю, что уже есть принятый ответ на эту проблему, но я все равно попытаюсь ответить в жидкой манере. Предполагать :

 The length of the Path is 'X+B' where 'B' is the length of the looped path and X of the non looped path. Speed of tortoise : v Speed of hare : 2*v Point where both meet is at a distance 'x + b - k' from the starting point. 

Теперь пусть зайц и черепаха встречаются после времени «t» с самого начала.

Замечания:

Если, Расстояние, пройденное черепахой = v * t = x + (bk) (скажем)

Тогда расстояние, пройденное зайцем = 2 * v * t = x + (b – k) + b (так как заяц уже пересек зацикленную часть)

Теперь время встречи одинаково.

=> x + 2 * b – k = 2 * (x + b – k)

=> x = k

Это, конечно, означает, что длина пути, который не зациклирован, такой же, как расстояние от начальной точки петли от точки, где они встречаются.

Interesting Posts
Давайте будем гением компьютера.