Middle of the Linked List

Лёгкая№876середина

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

876 Middle of the Linked ListРазбор · 1×

Пример: список 5 → 2 → 7 → 4 → 9 → 1 → 6 → 3, восемь узлов.

head52749163noneslow
slowfastсередина

slow = head, узел 5

01/16
сначала · назад · пуск · шаг
Скорость
1function middleNode(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 return slow
состояние
slow
5
fast
–
историянажмите шаг, чтобы вернуться

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

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

  1. За раунд fast делает два шага, а slow один, поэтому fast всегда вдвое дальше от головы, чем slow. Когда у fast кончается список, slow прошёл ровно половину.
  2. При чётной длине fast останавливается на none после n / 2 раундов: slow тогда на узле n / 2 + 1, втором из средних. При нечётной fast останавливается на последнем узле, а slow — на единственном среднем.
  3. Длину списка никто не считает: один проход, и когда остановиться, решает только условие цикла.

Сложность

Время O(n): fast проходит список один раз, по два узла за раунд, а slow — половину. Память O(1): два указателя.

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

Решить на LeetCode ↗

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