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

Ответ 1

Это алгоритм Floyd для определения цикла. Вы спрашиваете о втором этапе алгоритма - как только вы нашли node эту часть цикла, как найти начало цикла?

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

Когда черепаха и зайчик встречаются, мы нашли наименьшее я (количество шагов, сделанных черепахой), так что X _i= X _2i. Пусть mu представляет число шагов для перехода от X ₀ к началу цикла и пусть лямбда представляет длину цикла. Тогда я = mu + alambda и 2i = mu + blambda, где a и b являются целыми числами, обозначающими, сколько раз черепаха и зайчик обошли цикл. Вычитание первое уравнение из второго дает я = (b-a) * lambda, поэтому я является целочисленным кратным лямбда. Следовательно, X _{я + mu}= X _mu. X _i представляет собой место встречи черепахи и зайца. Если вы переместите черепаху обратно в стартовый node X ₀, и пусть черепаха и зайчик продолжатся с той же скоростью, после дополнительных шагов черепаха достигнет X _mu, и заяц достигнет X _{я + mu}= X _mu, поэтому вторая точка встречи обозначает начало цикла.

Ответ 2

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

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

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

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

На рисунке показан список с циклом. Цикл имеет длину n, и мы изначально m отходим от цикла. Также допустим, что место встречи k находится в нескольких шагах от начала цикла, и черепаха встречается, когда черепаха предприняла общие шаги i. (К тому времени заяц предпринял бы 2i всего шагов.).

Должны соблюдаться следующие 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. Он будет просто перемещать черепаху и зайца по одному шагу за раз, пока они не встретятся. Место встречи должно быть началом цикла, а количество шагов - расстоянием (м) до начала цикла. Предполагая, что мы знаем длину списка, мы также можем вычислить длину цикла вычитания m из длины списка.

Ответ 3

Обратитесь к этому изображению:

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

Расстояние, пройденное fastPointer до встречи= (x + y + z) + y                                                                               = x + 2y + z

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

Таким образом, используя простую скорость, соотношение времени и расстояния                    2 (x + y) = x + 2y + z              = > x + 2y + z = 2x + 2y              = > x = z

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

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

Ответ 4

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

Используя одно и то же изображение:

Скажем, быстрый бегун запустил цикл 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 прогонов цикла, а затем встречая другой указатель прямо в начале цикла.

Ответ 5

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

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

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

Ответ 6

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

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

Ответ 7

Подход:

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

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

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

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

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

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

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

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

Ответ 8

Итак, давайте предположим, что заяц и черепаха встречаются в точке, которая находится в шагах от начала цикла, количество шагов до начала цикла - это mu, а длина цикла равна L.

Итак, теперь на месте встречи →

Расстояние, покрытое черепахой = mu + a * L + k - Уравнение 1

(Шаги, предпринятые для достижения начала цикла + шаги, предпринятые для покрытия "а" итераций цикла + k шагов с начала цикла) (где a - некоторая положительная постоянная)

Расстояние, покрытое заяц = mu + b * L + k - Уравнение 2

(Шаги, предпринятые для достижения начала цикла + шаги, предпринятые для покрытия "b" итераций цикла + k шагов с начала цикла) (где b - некоторая положительная постоянная, а b >= a)

Таким образом, дополнительное расстояние, покрытое заяц, равно = Уравнение 2 - Уравнение 1 = (b-a) * L

Обратите внимание, что это расстояние также равно расстоянию от черепахи от начальной точки, так как заяц движется в 2 раза быстрее, чем черепаха. Это можно приравнять к "mu + k", который также является расстоянием от точки встречи с самого начала, если мы не будем включать множественные обходы цикла.

Таким образом, mu + k = (b-a) * L

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

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

Ответ 9

image кредит

Вызовите расстояние от числа ссылок, по которым следует указатель, и время количества итераций, которые алгоритм берет на перемещение медленного указателя на одну ссылку, и быстрый указатель на две ссылки. Есть N узлов перед циклом длины C, помеченным смещением цикла k = 0 по C- 1.

Чтобы достичь начала цикла, замедление занимает N времени и расстояния. Это означает, что скорость занимает N расстояние в цикле (N, чтобы туда добраться, N - вращение). Таким образом, в момент времени N медленное смещение цикла k = 0, а быстрое - при смещении цикла k = N mod C.

Если N mod C равно нулю, теперь медленное и быстрое совпадение, и цикл будет найден во время N и положение цикла k = 0.

Если N mod C не равен нулю, то быстро теперь приходится догонять медленное, которое в момент времени 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) в цикл.

// C++ pseudocode, end() is one after last element.

int t = 0;
T *fast = begin();
T *slow = begin();
if (fast == end()) return [N=0,C=0];
for (;;) {
    t += 1;
    fast = next(fast);
    if (fast == end()) return [N=(2*t-1),C=0];
    fast = next(fast);
    if (fast == end()) return [N=(2*t),C=0];
    slow = next(slow);
    if (*fast == *slow) break;
}

Хорошо, так что фаза 2: медленная принимает N дополнительных шагов для перехода к циклу, после чего быстро (теперь перемещение 1 за каждый шаг времени) находится на (C- (N mod C) +N) mod C = 0. Итак они встречаются в начале цикла после фазы 2.

int N = 0;
slow = begin();
for (;;) {
    if (*fast == *slow) break;
    fast = next(fast);
    slow = next(slow);
    N += 1;
}

Для полноты фаза 3 вычисляет длину цикла, перемещаясь еще раз через цикл:

int C = 0;
for (;;) {
    fast = next(fast);
    C += 1;
    if (fast == slow) break;
}

Ответ 10

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

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

• Возьмите два указателя (1= черепаха и 2= заяц), которые начинаются с головы ( O), 1 имеет длину шага 1, 2 имеет длину шага 2. Подумайте о моменте, когда 1 достигает старта node этого цикла ( 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.

  Например: if 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.

• Теперь мы сводим задачу к кругу. Вопрос: "Где место встречи?" . Где находится 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 - конечная точка).

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

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

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

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

Ответ 11

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

Ответ 12

Я не думаю, что это правда, что, когда они встречают эту отправную точку. Но да, если другой указатель (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;
}

Ответ 13

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

Анализ:

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

Чтобы найти начальную точку цикла, пусть...

• m - расстояние от головы до начала цикла;
• d - количество узлов в цикле;
• p1 - скорость медленного указателя;

• 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

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

Ответ 14

скажем,

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 должен быть шагом вперед)

Затем A пробегает k шагов, чтобы столкнуться с B, то есть A находится в N [k], B находится в N [m + 2k] (Примечание: B должен выполняться для шагов 2k, начиная с N [м])

A сталкивается B в N [k] и N [m + 2k] соответственно, это означает k = m + 2k, таким образом, k = -m

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

Просто говоря, нам просто нужно выполнить еще несколько шагов после того, как мы нашли столкновение node. У нас может быть указатель на запуск с начала и указатель, запускаемый из collision node, они будут встречаться при 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

Ответ 15

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

--After k шагов

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

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

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

(обратите внимание, что k == K == mod (loopsize, k) --e.g. Если узел занимает 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 встретились в начале цикла, вычислив длину цикла

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

--move указатель T2 в начало списка

--move длина указателя цикла

--move другой указатель H2 на голову

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

это!

Ответ 16

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

• Предположим, что расстояние от начала связанного списка до начала круга x hops. Позвольте называть начало круга как точку x (в шапках - см. Рисунок выше). Также предположим, что общий размер круга - N переходов.

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

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

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

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

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

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

Ответ 17

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

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

Ответ 18

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

Основными аха-моментами для меня были:

• Разделите T (черепаха) на T1 (предварительный цикл) и T2 (внутри цикл).

• Вычтите T из H, где они визуально перекрываются. То, что остается (H - T = H '), равно T.

• Оставшаяся математика довольно проста.

Ответ 19

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

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 + (b-k) (скажем)

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

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

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

= > x = k

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

Ответ 20

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

Ответ 21

Предположим, ваши указатели встречаются на пересечении точек y и z.

n и m - число циклов, которые быстрее и медленнее указатель занимает соответственно до встречи.

Обратитесь к изображению для остальной части доказательства. Найти начальную точку цикла в связанном списке