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