Как определить наличие цикла в связанном списке
Что проверяют
Знаете ли вы алгоритм Флойда и можете ли объяснить, почему указатели обязательно встретятся, а не просто воспроизвести код. Следом почти всегда просят найти узел, с которого начинается цикл, и назвать сложность.
Как отвечать
Начните с простого решения, потом улучшите:
HashSet<ListNode>: идём по списку и кладём узлы в множество, встретили уже виденный, значит цикл. Время O(n), память O(n);- Флойд, «черепаха и заяц»:
slowшагает на один узел,fastна два. Еслиfastилиfast.Nextдошёл доnull, цикла нет. Если цикл есть, оба указателя в него попадут, и расстояние между ними с каждым шагом сокращается на единицу, поэтому встреча гарантирована не позже чем за длину цикла. Время O(n), память O(1).
Условие while (fast != null && fast.Next != null) само отсекает пустой список, отдельная проверка head == null не нужна.
Продолжение, которое стоит знать заранее:
- начало цикла: после встречи ставим один указатель обратно на
headи двигаем оба по одному шагу. Они встретятся ровно в первом узле цикла, потому что путь от головы до входа равен пути от точки встречи до входа с точностью до целого числа оборотов; - длина цикла: от точки встречи идём по кругу, пока не вернёмся, и считаем шаги;
- алгоритм Брента: та же память O(1), обычно меньше обращений к узлам.
Проговорите крайние случаи: пустой список, один узел, ссылающийся сам на себя, цикл, который начинается не с головы.
Где спотыкаются
Сравнивают узлы через == или кладут в HashSet, не думая о равенстве. Если ListNode объявлен как record, сравнение идёт по значению, и на циклической структуре сгенерированный Equals уходит в бесконечную рекурсию. Надёжнее ReferenceEquals(slow, fast) и ReferenceEqualityComparer.Instance для множества.
Проверяют в цикле только fast != null и получают NullReferenceException на fast.Next.Next, когда список без цикла заканчивается.
Не могут объяснить, почему встреча неизбежна, и говорят «так работает алгоритм». Интервьюер почти наверняка попросит доказательство или начало цикла.