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

Question

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

Answer 1

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

Answer 2

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

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

• Разделить T (черепаха) на T1 (предварительная петля) и T2 (петля).

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

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

Answer 3

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

Answer 4

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

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

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

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

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

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

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

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

Answer 5

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

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

Answer 6

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

- после k шагов

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

----- H это k шагов в цикле (он пошел 2k всего и, следовательно, k в цикл)

** они теперь имеют размер петли - k отдельно

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

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

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

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

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

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

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

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

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

- переместить указатель на длину шага цикла

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

- перемещать Т2 и Н2 в тандеме, пока они не встретятся в начале цикла

вот и все!

Answer 7

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

Анализ:

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

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

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

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

Answer 8

скажем,

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 шагов дальше)

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

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

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

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

Answer 9

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

Answer 10

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

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

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