Linked List Cycle
Связный список хранится в массиве next: узел i ссылается на узел next[i], а -1 означает, что список здесь заканчивается. Голова списка — узел 0. Следуй по ссылкам от головы и верни true, если вернёшься к узлу, который уже посещал, или false, если дойдёшь до конца. Узлы, до которых обход никогда не доходит, не учитываются, даже если они ссылаются друг на друга, образуя цикл.
Функция
- nextinteger-array
- ссылка каждого узла: next[i] — это узел после узла i или -1
- Возвращаетboolean
- true, если обход от узла 0 повторно посещает узел, false, если достигает -1
Ограничения
1 ≤ next.length ≤ 104-1 ≤ next[i] ≤ next.length-1- Несколько узлов могут ссылаться на один и тот же узел, а некоторые узлы могут быть недостижимы из головного узла.
Примеры
- Ввод
- next = [1, 2, 3, 1]
- Вывод
- true
- Пояснение
- Обход идет по узлам 0, 1, 2, 3, а затем возвращается к 1. Узел 1 посещается дважды, поэтому в списке есть цикл через узлы 1, 2 и 3.
- Ввод
- next = [2, -1, 1]
- Вывод
- false
- Пояснение
- Путь проходит через 0, 2, 1, а затем достигает
-1: три разных узла, после чего наступает конец, поэтому цикла нет.
- Ввод
- next = [-1, 2, 1]
- Вывод
- false
- Пояснение
- Узел 0 ссылается на
-1, поэтому список состоит из одного узла. Узлы 1 и 2 ссылаются друг на друга в цикле, но обход от головы списка до них никогда не доходит.
+16 скрытых тестов при отправке
Дополнительный вопрос
Можешь также найти узел, с которого начинается цикл, используя по-прежнему дополнительную память O(1)?
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
Идите от узла 0, следуя по
next. Список без цикла останавливается на-1, а список с циклом никогда не останавливается. Что нужно запоминать, чтобы заметить, что вы ходите по кругу?Отмечать посещённые узлы работает, но для этого нужна память для каждого узла. Вместо этого пустите по списку два указателя с разной скоростью. Что произойдёт с расстоянием между ними, если в списке есть цикл?
Перемещайте
slowна один узел, аfast— на два узла за раунд. Еслиfastилиnext[fast]равен-1, цикла нет. Если оба указателя когда-либо укажут на один и тот же узел, цикл есть.
Решение
Список без цикла достигает -1 за n переходов по ссылкам, а список с циклом никогда не заканчивается, поэтому ждать конца нельзя. Нужно найти способ заметить, что обход идёт по кругу. Запоминание каждого посещённого узла требует O(n) памяти. Быстрые и медленные указатели Флойда справляются с этим с помощью двух целых чисел, потому что указатель, движущийся вдвое быстрее, должен догнать медленный внутри цикла.
Отмечайте посещённые узлы
Идея
Идите от узла 0 и отмечайте каждый узел, когда покидаете его. Если вы приходите в уже отмеченный узел, значит, вы вернулись к нему, и дальше это будет повторяться бесконечно: это цикл. В примере 1 вы отмечаете 0, 1, 2 и 3, а ссылка из узла 3 ведёт к узлу 1, который уже отмечен.
Узлы нумеруются от 0 до n-1, поэтому в качестве множества посещённых узлов подойдёт булев массив длины n. В связанном списке, построенном из объектов, ссылки на узлы можно было бы хранить в хеш-множестве; идея та же.
Каждый узел отмечается не более одного раза, а обход останавливается при первом повторе или при достижении -1, поэтому он занимает не более n шагов: время O(n) и память O(n) для отметок.
Алгоритм
- Создай булев массив
visitedдлиныn, состоящий из значений false. - Установи
node = 0. - Пока
nodeне равен-1, возвращайtrue, еслиvisited[node]уже равно true. - Иначе установи
visited[node]и перейди кnext[node]. - Когда обход достигнет
-1, возвращайfalse.
def hasCycle(next):
visited = [False] * len(next)
node = 0
while node != -1:
if visited[node]:
return True # back at a node already on the path
visited[node] = True
node = next[node]
return FalseБыстрый и медленный указатели (обнаружение цикла Флойда)
Идея
Установите два указателя в начало. slow проходит по одной ссылке за раунд, а fast — по две. Если список заканчивается, fast первым достигает -1, и вы возвращаете false. Если в списке есть цикл, fast первым входит в него и продолжает двигаться по кругу, пока туда не попадёт и slow.
Когда оба указателя оказываются в цикле, за каждый раунд fast проходит ровно на один узел больше, чем slow. Расстояние, которое fast ещё нужно пройти, чтобы достичь slow, уменьшается на единицу за каждый раунд, поэтому оно становится равным нулю, и указатели оказываются на одном узле. Поскольку fast приближается на один узел за раз, он никогда не сможет перепрыгнуть через slow.
В примере 1 после одного раунда slow находится на узле 1, а fast — на узле 2. После двух раундов slow находится на узле 2, а fast проходит узлы 3 и 1. После трёх раундов оба указателя находятся на узле 3, поэтому ответ — true.
Указателю slow требуется не более n раундов, чтобы войти в цикл, а оказавшись внутри, указатели встретятся до того, как он завершит один оборот, поэтому временная сложность составляет O(n). Для хранения нужны только номера двух узлов.
Алгоритм
- Установи
slow = 0иfast = 0. - Пока
fastне равен-1иnext[fast]не равно-1, перемещайslowна один переход, аfast— на два. - После каждого перемещения возвращай
true, если они находятся на одном узле. - Когда цикл остановится,
fastдостиг конца: возвращайfalse.
def hasCycle(next):
slow = 0
fast = 0
# fast needs two links to move; if either is missing, the list ends.
while fast != -1 and next[fast] != -1:
slow = next[slow]
fast = next[next[fast]]
if slow == fast:
return True
return False
Ловушки и крайние случаи
Ошибки здесь связаны с концом списка и с тем, какие узлы учитываются.
- Перемещение
fastна два перехода без проверки обоих. Иfast, иnext[fast]должны быть реальными узлами, прежде чем читатьnext[next[fast]]; иначе вы прочитаетеnext[-1], что приводит к сбою в большинстве языков и незаметно возвращает последний элемент в Python. - Сравнение указателей до их перемещения. Оба начинаются с узла 0, поэтому проверка в начале цикла обнаруживает цикл в каждом списке.
- Проверка всего массива вместо пути обхода. В
[-1, 2, 1]узлы 1 и 2 образуют цикл, но путь от головы заканчивается сразу, поэтому ответ —false. Также неверно проверять, повторяется ли значение вnext: в[4, 4, 4, 4, -1]несколько узлов ведут к узлу 4, но цикла нет. - Предположение, что цикл должен вести обратно к голове. В
[1, 2, 3, 4, 4]последний узел ведёт сам к себе, а в[0]так ведёт себя голова.
Частые вопросы4
Как работает алгоритм Флойда для обнаружения циклов?
Два указателя начинают движение от головы: один проходит по одной ссылке за шаг, другой — по две. Если цикла нет, быстрый указатель достигает конца. Если цикл есть, оба указателя в итоге оказываются внутри него, быстрый сокращает расстояние на один узел за шаг, и они встречаются на одном и том же узле.
Какова временная и пространственная сложность задачи «Цикл в связном списке»?
Оба подхода работают за время O(n), поскольку каждый узел проходит ограниченное число раз. Для отметки посещённых узлов требуется дополнительная память O(n). Быстрый и медленный указатели Флойда требуют O(1): два номера узлов.
Почему быстрый указатель не может перепрыгнуть через медленный?
Внутри цикла за каждый раунд fast перемещается на два узла, а slow — на один, поэтому расстояние, которое fast ещё должен пройти, чтобы достичь slow, уменьшается ровно на единицу. Расстояние, которое уменьшается на единицу за раунд, проходит значения 3, 2, 1, 0 и не может стать меньше нуля, поэтому два указателя встречаются на одном узле.
Можешь ли ты обнаружить цикл, считая шаги?
В этой форме массива — да: список без цикла достигает -1 не более чем за n переходов, поэтому если пройти n переходов и не достичь конца, это доказывает наличие цикла, используя O(1) памяти. Для этого нужно знать количество узлов, но список, состоящий из указателей, этого не сообщает, а предварительный подсчёт никогда не завершится, если в списке есть цикл. Метод Флойда не требует подсчёта.
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
Python
def hasCycle(next):
# Напишите код здесьСлучай 1
Случай 2
Случай 3
Ввод
next = [1, 2, 3, 1]
Ожидается
true