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