3622
правки
Изменения
→Реализация за O(n \log n)
Будем последовательно идти от начала цикла и проверять, лежит ли этот элемент на цикле. На каждой итерации запустим от текущего элемента вперёд указатель. Если он окажется в текущем элементе, прежде чем два раза посетит <tex>pointMeeting</tex>, то точку окончания (начала) хвоста нашли.
====Реализация за <tex>O(n \log n)</tex>====
Реализацию, приведенную выше можно улучшить. Для этого воспользуемся бинарным поиском. Сначала проверим голову списка, потом сделаем <tex> 2 </tex> шага вперёд, потом <tex> 4</tex>, потом <tex> 8 </tex> и так далее, пока не окажемся на цикле. Теперь у нас есть две позиции {{---}} на левой границе, где мы в хвосте, и на правой {{---}} в цикле. Сделаем бинарный поиск уже по этому отрезку и таким образом найдём цикл за <tex>O(n \log n)</tex>.
===Эффективная реализация===
Возможны два варианта цикла в списке. Первый вариант {{---}} сам список циклический (указатель <tex>next</tex> последнего элемента равен первому), а второй вариант {{---}} цикл внутри списка (указатель <tex>next</tex> последнего элемента равен любому другому (не первому). В первом случае найти длину цикла тривиально, во второй случай сводится к первому, если найти указатель на начало цикла. Достаточно запустить один указатель из <tex>pointMeeting</tex>, а другой из головы с одной скоростью. Элемент, где оба указателя встретятся, будет началом цикла. Сложность алгоритма {{---}} <tex>O(n)</tex>.
