Код Middle Связные списки обновлено
Цикл в списке
Условие
Есть ли цикл в односвязном списке? Узел: { value, next }.
Что проверяют тесты
цикл есть
цикла нет
пустой список
Как подойти
Алгоритм Флойда, O(1) памяти против O(n) у решения через Set. Условие цикла while (fast && fast.next) закрывает и пустой список, и чётную длину. Follow-up - найти начало цикла: после встречи один указатель возвращают в голову и двигают оба по шагу.
Подсказки: 2
- Два указателя с разной скоростью обязательно встретятся внутри цикла.
- Проверять надо и fast, и fast.next.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.