Середина
Проблема
Учитывая связанный список, верните узел, с которого начинается цикл. Если цикла нет, вернуть null
.
Примечание. Не изменяйте связанный список.
Последующие действия:
Сможете ли вы решить эту проблему, не занимая лишнего места?
Решение
Используйте два указателя с разной скоростью, скажем runner
и walker
, и сделайте runner
в два раза быстрее, чем walker
. Если в этом связанном списке нет цикла, runner
, наконец, будет проходить через весь список без соответствия walker
.
Если существует цикл, они встретятся друг с другом в узле, скажем, x
, а x
представляет x
-й узел в этом списке. Предположим, что позиция начала цикла находится на y
-м узле, а длина цикла равна m
.
- Что касается
runner
, он уже выполнил2x
узлов, что равноy + m + (x — y)
(длина до начала цикла + длина цикла + узлов для соответствияwalker
). Итак, у нас есть2x = y + m + (x — y)
, и он может вести кx = m
. - Что касается
walker
, ему нужно пройти большеm — (x — y) = m — x + y
узлов, чтобы достичь начала цикла. Как мы знаем в 1, чтоx
равноm
,walker
необходимо пройти большеy
узлов, чтобы достичь узла начала цикла.
Полями 1 и 2 мы можем поместить другой указатель, скажем, seeker
, с той же скоростью, что и walker
, в начале. Поскольку seeker
также необходимо y
перемещать узлы, чтобы достичь узла начала цикла, узел, который seeker
и walker
встречаются друг с другом, будет тем, что мы ищем.
Сложность
Пусть n
обозначает подсчет всех узлов в этом связанном списке, x
обозначает, что x
-й узел - это узел, который runner
соответствует walker
, а y
обозначает узел, с которого начинается цикл.
- Если в этом связанном списке нет цикла, то
runner
проходит через весь список за O (n / 2) времени. - Если в связанном списке существует цикл,
runner
необходимо время O (x), чтобы соответствоватьwalker
. И после того, как они встретятся друг с другом, требуется O (y) времени, чтобы позволитьseeker
встретитьсяwalker
. Таким образом, потребуется время O (x + y) = O (n + n) = O (n), потому чтоx
иy
меньше n.
Из пунктов 1 и 2 видно, что для обнаружения узла начала цикла требуется O (n / 2 + n) = O (n) времени.
Для сложности пространства используется только O (1) дополнительное пространство.