Почему точка встречи в цикле имеет такое же количество шагов, что и начало связанного списка?

Question

Существует, очевидно, стандартный подход, чтобы найти, есть ли в связанном списке цикл, а затем вернуть узел, находящийся в начале цикла, который является алгоритмом Флой с медленными / быстрыми указателями.
Код и логикаclear, исключая 1 вещь.
Подход основан на предположении, что узел в цикле, с которым встретятся указатели, будет точно таким же числом шагов, что и от начала списка до начала цикла.Это часть, которую я не получаю.
Так что, если Slow и Fast оба начинаются в начале списка, когда Slow делает k шагов и достигает начала цикла, Fast сделает 2k шагов и будет эффективно kшаги в цикле.
Так быстро впереди медленного на k шагов и позади медленного (который находится в начале цикла) N - k, где N - размер цикла.
Так как на каждом шаге быстрое приближениемедленное и быстрое отстает от медленного N - k узлов, быстрое достигнет медленного за N - k шагов.
В этот момент медленный сделал бы N - k шагов и будет в узле N - k.
Fastсделал бы 2 (N - k) шагов и был бы в узле 2N - 2k + k = 2N - k (так как быстрый был в узле k).
Так как это цикл 2N - k = N - k и, следовательно,они встречаются в узле N - k.
Но почему N - k узел k находится в шаге от начала цикла?
Что я здесь недопонимаю?

Answer 1

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

Переменные, используемые для объяснения:

• N -общее количество узловых ссылок в связном списке.
• C - расстояние от головы до начальной точки цикла
• Y - расстояние от начала цикла до точки встречи.
• K - расстояние от точки встречи до начала цикла.

Итак, мы можем сделать некоторые выводы из этих переменных.

1. N = C + Y + K
2. Расстояние, пройденное медленным указателем - Ds = C + Y
3. Расстояние, пройденное быстрым указателем - Df = N + Y

Здесь

• N = 12
• C = 2
• Оба указателя встретятся в узле номер 11, поэтому Y = 8
• K = 2

Поскольку мы знаем, что быстрый указатель в 2 раза быстрее медленного, поэтому Df = 2 * Ds

Используя связь между Df и Ds и помещая туда значения сверху

N + Y = 2 * ( C + Y )

N + Y = 2*C + 2*Y

N = 2*C + Y

Используя другое отношение N,

C + Y + K = 2*C + Y

K = C

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

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

Надеюсь, это поможет.

Продолжайте спрашивать,продолжай расти :) 1058 *

Answer 2

Вот то, что вам не хватает.

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

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

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

РЕДАКТИРОВАТЬ Я объяснял, как работает обнаружение цикла, а некак работает обнаружение головы.Вот альтернативное объяснение этого.Другими словами.

Предположим, у нас есть цепочка из i узлов, ведущих к петле длиной j.Мы изначально бегаем быстро + медленные указатели, и они встречаются.Для того, чтобы встретиться, пост должен обходиться в цикле в целое число раз больше, чем медленный.Таким образом, они встречаются после k*j шагов.

В этот момент медленный указатель прошел всего k*j шагов, из которых i шагов достигло петли, поэтому он прошел k*j-i шагов внутрицикл.

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