Существует этот, по-видимому, стандартный подход, чтобы найти, есть ли в связанном списке цикл, а затем вернуть узел, который находится в начале цикла, который является алгоритмом floy с медленными/быстрыми указателями.
Код и логика ясны, кроме 1 вещь.
Подход основан на предположении, что узел в цикле, с которым встретятся указатели, проходит точно такое же количество шагов, как от начала списка до начала цикла. Это то, чего я не понимаю.
Итак, если Медленный и Быстрый оба начинаются в начале списка, когда Медленный делает k шагов и достигает начала цикла, Быстрый сделает 2k шагов и фактически станет k шагов в цикле.
Таким образом, быстрый опережает медленный на k шагов и отстает от медленного (который находится в начале цикла) N - k, где N - размер цикла.
Поскольку на каждом шаге быстрый приближается медленный и быстрый отстают от медленного на N - k узлов, быстрый достигнет медленного через N - k шагов.
В этот момент медленный сделает N - k шагов и будет в узле N - k.
Быстрый сделал бы 2(N - k) шагов и оказался бы в узле 2N - 2k + k = 2N - k (поскольку fast был в узле k).
Поскольку это петля 2N - k = N - k и, следовательно, они встречаются в узле N - k.
Но почему N - k узла k шагов от начала цикла?
Что я здесь неправильно понимаю?
Почему точка встречи в цикле состоит из того же количества шагов, что и начало связанного списка?
Ответы (2)
Вот чего вам не хватает.
Всякий раз, когда оба указателя находятся в цикле, а быстрый указатель кратен длине цикла впереди, быстрый указатель пересекает медленный целое число раз, и они находятся в одном и том же месте. Если вы продолжите, они разделятся и снова будут плескаться. И опять. И опять.
Вся причина, по которой алгоритм работает, заключается в этом притирочном поведении.
Их первая встреча может быть строго кратной длине цикла. Например, если у вас есть цепочка из 24 узлов, ведущая к циклу длиной 7, то они впервые встретятся через 28 шагов.
EDIT Я объяснял, как работает обнаружение цикла, а не как работает обнаружение головы. Вот альтернативное объяснение этому. Другими словами.
Предположим, у нас есть цепочка из i узлов, ведущая к циклу длиной j. Сначала мы запускаем быстрые + медленные указатели, и они встречаются. Чтобы встретиться, быстрый должен пройти по петле некоторое целое число раз больше, чем медленный. Итак, они встречаются через k*j шагов.
В этот момент медленный указатель прошел всего k*j шагов, из которых i шагов попадало в цикл, поэтому он прошел k*j-i шагов внутри цикла.
Теперь мы ставим быстрый указатель в начало и продвигаемся вперед с той же скоростью. Еще через i шагов указатель в начале достиг цикла. Тем временем медленный указатель ранее прошел k*j-i шагов внутри цикла, а теперь прошел еще i шагов за k*j шагов внутри цикла. Поскольку k*j кратно длине цикла, он также возвращается в начало, и они снова встречаются.
k*j шагах, что означает кратность цикла, почему в это число входит i? Мне кажется, что после i шагов и при переходе к началу цикла медленное встречается с быстрым через k*j шагов. 2) Кроме моего предыдущего вопроса о i то, что вы описываете, отвечает на то, что я спрашиваю, но я не понимаю, где ошибка в рассуждениях, которые я описываю в своем посте. Кажется, что N - k, которое у меня есть, совпадает с k*j, которое вы говорите, но выражение его таким образом показывает, что необходимо k шагов. Но N - k - k дает N, и поэтому мне не ясно, в чем ошибочность моих рассуждений.
- person Jim; 30.05.2018
k*j шагах, потому что это когда быстрый цикл проходит в целое число раз больше, чем медленный. i входит в него, потому что именно столько шагов необходимо на пути к петле.
- person btilly; 30.05.2018
k*j шага от начального указателя. Быстрый указатель переместился на 2k*j шага от начального указателя. Таким образом, пост прошел цикл дополнительно j раза. И медленный прошел i шага, чтобы добраться до петли, и только k*j - i шагов внутри петли. Запишите несколько небольших примеров и проследите их, чтобы проверить.
- person btilly; 30.05.2018
Позвольте мне дать вам другой взгляд на эту проблему, и, в конце концов, вы тоже можете получить ответ.
Переменные, используемые для объяснения:
- N - общее количество ссылок на ноды в LinkedList.
- C - расстояние от головы до начальной точки петли
- Y - расстояние от начала петли до точки встречи.
- K - расстояние от точки встречи до начала петли.
Таким образом, мы можем сделать некоторые выводы из этих переменных.
- N = C + Y + K
- Расстояние, пройденное медленным указателем - Ds = C + Y
- Расстояние, пройденное быстрым указателем - 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
Отсюда следует, что расстояние между головой и началом цикла равно расстоянию между узлом точки встречи и началом цикла.
Постарайтесь понять это и всегда старайтесь упростить задачу, разбивая ее на более мелкие части.
Надеюсь, это поможет.
Продолжайте спрашивать, продолжайте расти :)
A -> B -> C -> D -> E -> F -> G -> H -> I -> J -> K -> D- person Jim schedule 30.05.2018