Reverse Linked List II

Средняя№92разворот

Дан связный список и две позиции, left и right, считая с 1. Нужно развернуть только узлы с позиции left по позицию right, остальное оставить как есть и вернуть начало. Наш пример: 3 → 8 → 1 → 6 → 4 → 2, left = 2, right = 5 — ответ 3 → 4 → 6 → 1 → 8 → 2.

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

Пример: развернуть позиции 2..5 в 3 → 8 → 1 → 6 → 4 → 2: отрезок 8 → 1 → 6 → 4.

nonedummy381642
не трогаемbefore, перед отрезкомcurnext, запомнилиразвёрнуты

Фиктивный узел перед головой: перед отрезком всегда есть узел, даже если отрезок начинается с головы

01/30
сначала · назад · пуск · шаг
Скорость
1function reverseBetween(head, left, right):
2 dummy = new node whose next is head
3 before = dummy
4 repeat left - 1 times:
5 before = before.next
6 first = before.next
7 prev = none
8 cur = first
9 repeat right - left + 1 times:
10 next = cur.next
11 cur.next = prev
12 prev = cur
13 cur = next
14 before.next = prev
15 first.next = cur
16 return dummy.next
состояние
before
–
first
–
prev
–
cur
–
next
–
историянажмите шаг, чтобы вернуться

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

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

  1. before останавливается на узле перед отрезком, а фиктивный узел гарантирует, что такой есть: при left = 1 before остаётся на dummy, и dummy.next становится новым началом.
  2. Внутри отрезка — цикл разворота с карточки, ровно right − left + 1 раз; после него cur стоит на первом узле за отрезком.
  3. Две ссылки пришивают отрезок обратно: before → prev, его новый первый узел, и first, теперь его последний узел, → cur. Остальные ссылки не меняются.

Сложность

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

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

Решить на LeetCode ↗

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