Выбор ответа Middle Связные списки спрашивают часто обновлено
Есть ли цикл в списке
Вопрос
Как определить цикл в односвязном списке с O(1) памяти?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Указатели Флойда: быстрый догонит медленного. Быстрый делает 2 шага, медленный 1.
Варианты ответа
- Set посещённых узлов: повтор значит цикл
- Указатели Флойда: быстрый догонит медленногоправильный ответ
- Посчитать длину списка и сравнить с числом узлов
- Развернуть список и сравнить головы до и после
Разбор
Быстрый делает 2 шага, медленный 1. В цикле быстрый догоняет медленного на 1 узел за шаг и обязательно встретит его. Без цикла быстрый дойдёт до null. O(n) времени, O(1) памяти.
- Set работает, но O(n) памяти.
- Длину списка с циклом не посчитать: обход бесконечен.
- Разворот меняет список и даёт хитрый признак, но это не стандартный ответ и портит входные данные.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.