Reverse Linked List

Лёгкая№206разворот

Дан первый узел односвязного списка. Нужно развернуть список, чтобы каждая ссылка смотрела в обратную сторону, и вернуть новое начало. Наш пример: 4 → 7 → 2 → 9 — ответ 9 → 2 → 7 → 4.

206 Reverse Linked ListРазбор · 1×

Пример: развернуть 4 → 7 → 2 → 9 на месте.

nonenone4729prevhead
ещё не дошлиcurnext, запомнилиразвёрнуты, начало в prev

prev = none: пока ничего не развёрнуто

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

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

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

  1. next запоминаем до того, как перезаписать cur.next, поэтому остаток списка не теряется: другого пути к нему нет.
  2. Всё левее cur уже развёрнуто и начинается с prev; каждый шаг переносит один узел из старого списка в начало развёрнутого.
  3. Старая голова оказывается последней и указывает на none, а head всё ещё смотрит на неё. Новое начало — последний узел, до которого дошёл prev.

Сложность

Время O(n): один проход, каждый узел разворачиваем один раз. Память O(1): три указателя, новых узлов нет.

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

Решить на LeetCode ↗

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