Изменения
Нет описания правки
Очевиден случай, когда необходимо добавить элемент (<tex>newHead</tex>) в голову списка. Установим в этом элементе ссылку на старую голову, и обновим указатель на голову.
'''function''' insert(newHead): newHead.next = head head = newHead [[Файл:insertHead.png|center|550px]]Если же на нужно вставить элемент (<tex>thatElement</tex>) в определенную позицию после какого-то другого элемента (<tex>thisElement</tex>), то просто изменим соответствующие ссылки. '''function''' insertAfter(thisElement, Node thatElement):
thatElement.next = thisElement.next
thisElement.next = thatElement
===Поиск===
Для того, чтобы найти элемент по значению (<tex>value</tex>), будем двигаться по списку от головы до конца и сравнивать значение в элементах с искомым. Если элемента в списке нет, то возвращаем <tex>NULL</tex>.
Node search('''int''' value):
node = head
'''while''' node != ''NULL'' '''and''' value != node.value
[[Файл:removeHead.png|center|430px]]
Удаление элемента после заданного (<tex>thisElement</tex>) происходит следующим образом: изменим ссылку на следующий элемент на следующий за удаляемым, затем удалим нужный объект.
'''function''' removeAfter(Node thisElement):
'''if''' thisElement.next != ''NULL''
tmp = thisElement.next
[[Файл:removeAfter.png|center|550px]]
==Задача на поиск Поиск цикла в списке==
Для начала необходимо уметь определять {{---}} список циклический или нет. Воспользуемся алгоритмом Флойда "Черепаха и заяц". Пусть за одну итерацию первый указатель (черепаха) переходит к следующему элементу списка, а второй указатель (заяц) на два элемента вперед. Тогда, если эти два указателя встретятся, то цикл найден, если дошли до конца списка, то цикла нет.
'''boolean''' hasCycle(Node head):
'''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>, то точку окончания (начала) хвоста нашли.
'''int''' getTail(Node head, Node pointMeeting):
lengthTail = 0
currentElement = head
'''while''' true
iterator = currentElement.next
count = 0
'''while''' iterator != currentElement '''and''' count != 2
'''if''' iterator == pointMeeting
count++
iterator = iterator.next
'''if''' count < 2
'''break'''
currentElement = currentElement.next
lengthTail++
'''return''' lengthTail
===Реализация за <tex>O(n \log n)</tex>===Реализацию, приведенную выше можно улучшить. Для этого воспользуемся бинарным поиском. Сначала проверим голову списка, потом сделаем 2 шага вперёд, потом 4, потом 8 и так далее, пока не окажемся на цикле. Теперь у нас есть две позиции {{---}} на левой границе, где мы в хвосте, и на правой {{---}} в цикле. Сделаем бинарный поиск уже по этому отрезку и таким образом найдём цикл за <tex>O(n \log n)</tex>.===Эффективная реализация===Возможны два варианта цикла в списке. Первый вариант {{---}} сам список циклический (указатель <tex>next</tex> последнего элемента равен первому), а второй вариант {{---}} цикл внутри списка(указатель <tex>next </tex> последнего элемента равен любому другому (не первому). В первом случае найти длину цикла тривиально, во второй случай сводится к первому, если найти указатель на начало цикла. Для того, чтобы его найти, запомним момент, когда в предыдущей функции два указателя оказались равны друг другу. Теперь достаточно Достаточно запустить один указатель из этого места списка<tex>pointMeeting</tex>, а другой из головы с одной скоростью. Элемент, где оба указателя встретятся, будет началом цикла. Сложность алгоритма {{---}} <tex>O(n)</tex>.
Ниже приведена функция, которая находит эту точку, а возвращает длину хвоста списка.
'''int''' getTail(Node head, Node pointMeeting):
lengthTail = lenghtTail + 1
'''return''' lengthTail
====Доказательство корректности алгоритма====
Рассмотрим цикл длиной <tex>N</tex> с хвостом длины <tex>L</tex>. Напишем функции для обоих указателей в зависимости от шага <tex>n</tex>. Очевидно, что встреча не может произойти при <tex>n \leqslant L</tex>, так как в этом случае <tex>2n>n</tex> для любого <tex>n>0</tex>. Тогда положения указателей зададутся следующими функциями (при <tex>n>L</tex>):
==Задача про обращение списка==
Для того, чтобы обратить список, необходимо пройти по всем элементам этого списка, и все указатели на следующий элемент заменить на предыдущий.
Эта рекурсивная функция принимает указатель на голову списка и предыдущий элемент (при запуске указывать <tex>NULL</tex>), а возвращает указатель на новую голову списка.
==См.также==
