13
правок
Изменения
м
===Реализация за <tex>O(n \log n)</tex>===
Реализацию, приведенную выше можно улучшить. Для этого воспользуемся бинарным поиском. Сначала проверим голову списка, потом сделаем 2 шага вперёд, потом 4, потом 8 и так далее, пока не окажемся на цикле. Теперь у нас есть две позиции {{---}} на левой границе, где мы в хвосте, и на правой {{---}} в цикле. Сделаем бинарный поиск уже по этому отрезку и таким образом найдём цикл за <tex>O(n \log n)</tex>.
Поправка пунктуации.
'''return''' ''false''
tortoise = tortoise.next
hare = hairhare.next.next '''until''' tortoise !== hare
'''return''' ''true''
Если цикла не существует, то заяц первым дойдет до конца и функция возвратит <tex>false</tex>. В другом случае, в тот момент, когда и черепаха и заяц находятся в цикле, расстояние между ними будет сокращаться на <tex>1</tex> (так как <tex>2</tex> (скорость зайца) <tex>- 1</tex> (скорость черепахи) <tex>= 1</tex>), что гарантирует их встречу за конечное время.
==Поиск длины хвоста в списке с циклом==
Так как для поиска хвоста мы должны знать, что цикл существует, воспользуемся предыдущей функцией и при выходе из неё запомним "момент встречи" зайца и черепахи. Назовем её <tex>pointMeeting</tex>.
===Наивные реализации=======Реализация за <tex>O(n^2)</tex>====Будем последовательно идти от начала цикла и проверять, лежит ли этот элемент на цикле. На каждой итерации запустим от текущего элемента <tex>pointMeeting</tex> вперёд указатель. Если он окажется в текущем элементе, прежде чем два раза посетит <tex>pointMeeting</tex>снова, то точку окончания (начала) хвоста нашли. '''int''' getTail(Node head, Node pointMeeting): lengthTail = 0 currentElement = head '''while''' true iterator = currentElement.next count = 0 '''while''' iterator !Реализация за <tex>O(n \log n)</tex>= currentElement '''and''' count != 2 '''if''' iterator == pointMeeting count++ iterator = iteratorРеализацию, приведенную выше можно улучшить. Для этого воспользуемся [[Целочисленный_двоичный_поиск | бинарным поиском]].next '''if''' count Сначала проверим голову списка, потом сделаем < tex> 2 '''break''' currentElement = currentElement</tex> шага вперёд, потом <tex> 4 </tex>, потом <tex> 8 </tex> и так далее, пока не окажемся на цикле. Теперь у нас есть две позиции {{---}} на левой границе, где мы в хвосте, и на правой {{---}} в цикле. Сделаем бинарный поиск уже по этому отрезку и таким образом найдём цикл за <tex>O(n \log n)</tex>.next lengthTail++ '''return''' lengthTail
===Эффективная реализация===
Возможны два варианта цикла в списке. Первый вариант {{---}} сам список циклический (указатель <tex>next</tex> последнего элемента равен первому), а второй вариант {{---}} цикл внутри списка (указатель <tex>next</tex> последнего элемента равен любому другому (не первому)). В первом случае найти длину цикла тривиально, во второй случай сводится к первому, если найти указатель на начало цикла. Достаточно запустить один указатель из <tex>pointMeeting</tex>, а другой из головы с одной скоростью. Элемент, где оба указателя встретятся, будет началом цикла. Сложность алгоритма {{---}} <tex>O(n)</tex>.
Ниже приведена функция, которая находит эту точку, а возвращает длину хвоста списка.
'''int''' getTail(Node head, Node pointMeeting):
Приравнивая, получим <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>
Известно, что
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]
[[Категория: Структуры данных]]
