Изменения
→Задача на поиск цикла в списке
==Задача на поиск цикла в списке==
Для начала необходимо уметь определять {{---}} список циклический или нет. Воспользуемся алгоритмом Флойда "Черепаха и заяц". Пусть за одну итерацию первый указатель (черепаха) переходит к следующему элементу списка, а второй указатель (заяц) на два элемента вперед. Тогда, если эти два указателя встретятся, то цикл найден, если дошли до конца списка, то цикла нет.
'''boolean''' isCyclehasCycle(head):
tortoise = head
hare = head
'''return''' ''true''
Возможны два варианта цикла в списке. Первый вариант {{---}} сам список циклический(указатель next последнего элемента равен первому), а второй вариант {{---}} цикл внутри списка(указатель next последнего элемента равен любому другому(не первому). В первом случае найти длину цикла тривиально, во второй случай сводится к первому, если найти указатель на начало цикла. Для того, чтобы его найти, запомним момент, когда в предыдущей функции два указателя оказались равны друг другу. Теперь достаточно запустить один указатель из этого места списка, а другой из головы с одной скоростью. Элемент, где оба указателя встретятся, будет началом цикла.
Ниже приведена функция, которая находит эту точку, а возвращает длину хвоста списка.
'''int''' getTail(head, pointMeeting):
