Premium

Быстрый и медленный указатели

Цикл в связном списке

Проверить, есть ли цикл с помощью быстрого и медленного указателей

Легкий

Постановка задачи

Описание (LeetCode - 141. Linked List Cycle)

Дана голова связного списка head. Нужно определить, есть ли в списке цикл.

Цикл есть, если какой-то узел снова ссылается на один из предыдущих узлов списка.

Пример 1:

head -> 3 -> 2 -> 0 -> -4
             ^          |
             |          |
             +----------+

head = [3, 2, 0, -4], pos = 1

Результат:

true

Пояснение:

Последний узел указывает на узел с индексом 1.

Пример 2:

head = [1, 2], pos = 0

Результат:

true

Пример 3:

head = [1], pos = -1

Результат:

false

Ограничения:

  • Количество узлов в списке от 0 до 10⁴
  • -10⁵ <= Node.val <= 10⁵
  • pos не передается в функцию, он используется только для описания цикла

Решение

Простое решение - хранить все посещенные узлы в хеш-множестве. Если мы снова увидели тот же узел, значит цикл есть. Это работает за O(n), но требует O(n) дополнительной памяти.

Паттерн быстрого и медленного указателей позволяет решить задачу без дополнительной структуры данных.

Идея решения:

Запустим два указателя из головы списка:

  1. slow двигается на один узел за шаг.
  2. fast двигается на два узла за шаг.

Если цикла нет, fast дойдет до конца списка. Если цикл есть, оба указателя окажутся внутри кольца, и быстрый указатель догонит медленный.

Основные шаги:

  1. Инициализируем slow = head, fast = head.
  2. Пока fast и fast.next не равны null:
    • двигаем slow на один шаг;
    • двигаем fast на два шага;
    • если slow == fast, возвращаем true.
  3. Если цикл завершился, возвращаем false.

Почему нужно проверять fast.next? Потому что быстрый указатель делает два шага, и перед обращением к fast.next.next нужно убедиться, что следующий узел существует.

Этот алгоритм часто называют алгоритмом Флойда или "черепаха и заяц". Медленный указатель - черепаха, быстрый - заяц.

Оценка сложности

Временная сложность

В списке без цикла быстрый указатель пройдет список до конца. В списке с циклом встреча тоже произойдет за линейное число шагов.

Итоговая временная сложность: O(n).

Пространственная сложность

Мы используем только два указателя, поэтому дополнительная память равна O(1).

Код решения

Приведем код решения.

func hasCycle(head *ListNode) bool {
    slow := head
    fast := head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            return true
        }
    }
    return false
}

Итоги

Разная скорость движения позволяет обнаружить цикл без памяти на посещенные узлы. Если в списке есть цикл, быстрый указатель обязательно встретится с медленным. Если цикла нет, быстрый указатель дойдет до null.

Войдите чтобы отмечать прогресс