Почему это работает
- Все значения от 1 до n, поэтому каждая ссылка ведёт на настоящий индекс и ни одна — на 0: от 0 по ссылкам можно идти бесконечно, а индексов всего n + 1, значит, путь уходит в петлю.
- Петля начинается в индексе, в который ведут две ссылки: одна с хвоста, другая с конца петли. Этот индекс записан в двух ячейках, значит, он и есть повтор.
- Найти начало петли — это Linked List Cycle II: встретиться внутри, вернуть slow в начало и вести обоих по одному шагу. Массив только читаем, а вся память — два индекса.
Сложность
Время O(n): каждый цикл делает не больше примерно n шагов, как в Linked List Cycle II. Память O(1): два индекса, массив не меняется.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗