Где применяется
1. Задача
Ты идёшь по цепочке узлов { val, next }, и нужно ответить на один из двух вопросов. Первый: замыкается ли цепочка сама на себя, так что идти по next можно бесконечно? Второй ты уже решал в прошлом уроке: если петли нет, какой узел стоит посередине, когда длина заранее неизвестна?
Петля в цепочке бывает на практике. Планировщик задач связывает задания ссылками «выполнить после». Одна ошибка в настройке, и задача A ждёт B, а B ждёт A. Если идти по такой цепочке, ты никогда не остановишься. Планировщик зависает.
Первое, что приходит в голову: записывать каждый пройденный узел в множество (Set) и остановиться на первом узле, который встретился второй раз. Это работает, но на огромной цепочке множество вырастает до размера всего списка. Есть способ ответить на оба вопроса с помощью двух переменных.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитhasCycle(1 → 2 → 3 → 4 → 5 → 6 → back to 3)Есть ли в списке цикл? Последний узел, 6, указывает обратно на 3. Оба указателя стоят на голове.
Как узнать
Эти слова в условии значат этот паттерн
- обнаружить цикл в связном списке
- найти, где начинается цикл
- найти средний узел списка
- определить, является ли список палиндромом
- без доп. памяти / O(1) память, только указатели
Похоже, но не то
- Два указателя (в одну сторону) (Two pointers (same direction))
Там один указатель читает, а другой пишет. Здесь читают оба, но с разной скоростью.
- Хеш-множество / словарь (Hash set / map)
Множество посещённых узлов тоже ловит цикл. Оно стоит O(n) памяти вместо O(1).
- Разворот связного списка (Linked list reversal)
Разворот перевязывает сами ссылки. Этот приём не меняет в списке ни одного указателя.
- Обход графа BFS / DFS (Graph BFS / DFS)
Обход находит циклы в любом графе с множеством посещённых. Здесь работает то, что выход из узла один.
n до 1e6 даёт O(n) времени и O(1) памяти. Медленный указатель делает не больше n шагов.
На LeetCode
Задачи, где нужно понять, зацикливается ли переход по next и где начинается петля, в том числе когда петля спрятана в числах или значениях массива. Два бегуна с разной скоростью отвечают на это с O(1) памяти.
Это hasCycle из урока.
Это cycleEntry, где второй проход после встречи начинается с головы.
Шаг с суммой квадратов цифр работает как указатель next, и fast со slow покажут, дойдёшь ли ты до 1 или зациклишься.
Считай каждое значение указателем next, и вход в петлю окажется повторяющимся числом.