Середина

Проблема

Учитывая связанный список, верните узел, с которого начинается цикл. Если цикла нет, вернуть null.

Примечание. Не изменяйте связанный список.

Последующие действия:
Сможете ли вы решить эту проблему, не занимая лишнего места?

Решение

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

Если существует цикл, они встретятся друг с другом в узле, скажем, x, а x представляет x-й узел в этом списке. Предположим, что позиция начала цикла находится на y -м узле, а длина цикла равна m.

  1. Что касается runner, он уже выполнил 2x узлов, что равно y + m + (x — y) (длина до начала цикла + длина цикла + узлов для соответствия walker). Итак, у нас есть 2x = y + m + (x — y), и он может вести к x = m.
  2. Что касается 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 обозначает узел, с которого начинается цикл.

  1. Если в этом связанном списке нет цикла, то runner проходит через весь список за O (n / 2) времени.
  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) дополнительное пространство.