Изменения
→Поиск цикла в списке: repeat until, в отличие от do while продолжает работу при ложности условия
'''return''' ''false''
tortoise = tortoise.next
hare = hairhare.next.next '''until''' tortoise !== hare
'''return''' ''true''
Если цикла не существует, то заяц первым дойдет до конца и функция возвратит <tex>false</tex>. В другом случае, в тот момент, когда и черепаха и заяц находятся в цикле, расстояние между ними будет сокращаться на <tex>1</tex>, что гарантирует их встречу за конечное время.
===Наивные реализации===
====Реализация за <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>.
===Эффективная реализация===
Приравнивая, получим <tex>n \bmod N = 0</tex>, или <tex>n = k N, n > L</tex>.
Пусть <tex>H</tex> {{- --}} голова списка, <tex>X</tex> {{--- }} точка встречи, <tex>A</tex> {{--- }} первый элемент цикла, <tex>Q</tex> {{--- }} расстояние от <tex>X</tex> до <tex>A</tex>. Тогда в точку <tex>A</tex> можно прийти двумя путями: из <tex>H</tex> в <tex>A</tex> длиной <tex>L</tex> и из <tex>H</tex> через <tex>X</tex> в <tex>A</tex> длиной <tex>L + N = X + Q</tex>, то есть:
<tex>Q = L + N - X</tex>, но так как <tex>X = kN</tex>
<tex>Q = L + (1-k) N</tex>
Пусть <tex>L = p N + M, 0 <= \leqslant M < N</tex>
Известно, что
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]
[[Категория: Структуры данных]]
