Linked List Cycle II

Средняя№142цикл

Дана голова связного списка. Если его последний узел указывает назад, на один из прежних узлов, в списке петля: верни узел, с которого она начинается, — первый, к которому придёшь дважды. Если список кончается на none, верни none. Наш пример: 2 → 6 → 9 → 5 → 1 → 8 → 3, и 3 указывает обратно на 5 — ответ узел 5, индекс 3.

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

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

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

slow = head, узел 2

01/30
сначала · назад · пуск · шаг
Скорость
1function detectCycle(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 slow = head
9 while slow is not fast:
10 slow = slow.next
11 fast = fast.next
12 return slow
13 return none
состояние
slow
2
fast
–
историянажмите шаг, чтобы вернуться

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

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

  1. Пусть a — шагов от головы до начала петли, а L — длина петли. При встрече fast прошёл вдвое больше slow, и лишнее — это целые круги: slow прошёл кратное L.
  2. Значит, от места встречи ещё a шагов приведут slow в точку a + (кратное L), то есть в начало петли. Указатель с головы придёт туда за те же a шагов.
  3. Во втором цикле оба идут по одному шагу, поэтому впервые сходятся ровно в начале петли, не раньше: до него один ещё на хвосте, а другой на петле.

Сложность

Время O(n): первый цикл делает меньше n раундов, как в Linked List Cycle, а второй ровно a, длину хвоста. Память O(1): два указателя и никакого множества посещённых узлов.

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

Решить на LeetCode ↗

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