Linked List Cycle

Лёгкая№141цикл

Дана голова связного списка. Последний узел может указывать не на none, а назад, на один из прежних узлов, и тогда идти по списку можно бесконечно. Верни true, если в списке есть такая петля, и false, если он кончается. Наш пример: 4 → 9 → 1 → 7 → 3 → 8 → 6, и 6 указывает обратно на 1 — ответ true.

141 Linked List CycleРазбор · 1×

Пример: список 4 → 9 → 1 → 7 → 3 → 8 → 6, в котором 6 указывает обратно на 1.

head4917386slow
slowfastместо встречи

slow = head, узел 4

01/23
сначала · назад · пуск · шаг
Скорость
1function hasCycle(head):
2 slow = head
3 fast = head
4 while fast and fast.next are not none:
5 slow = slow.next
6 fast = fast.next.next
7 if slow is fast:
8 return true
9 return false
состояние
slow
4
fast
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Если список кончается, fast первым доходит до none, и цикл останавливается: false. Сначала проверяются fast и fast.next, поэтому fast.next.next от none никогда не берётся.
  2. Если в списке петля, оба указателя в итоге ходят по ней по кругу. За раунд fast делает два шага, а slow один, поэтому разрыв между ними сокращается ровно на один: перепрыгнуть slow fast не может, он встаёт на него.
  3. «slow is fast» сравнивает узлы, а не значения: в двух разных узлах может лежать одно и то же число.

Сложность

Время O(n): fast догоняет slow раньше, чем slow обойдёт петлю один раз, поэтому slow делает меньше n шагов, а fast меньше 2n. Память O(1): два указателя и никакого множества посещённых узлов.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.