Reverse Nodes in k-Group

Сложная№25разворот

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

25 Reverse Nodes in k-GroupРазбор · 1×

Пример: 4 → 1 → 7 → 3 → 9 → 2 → 8 → 5, k = 3: две целые группы и 2 узла в остатке.

nonedummy41739285
не трогаемbefore, перед группойпосчитаны / next, запомнилиcurразвёрнуты

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

01/78
сначала · назад · пуск · шаг
Скорость
1function reverseKGroup(head, k):
2 dummy = new node whose next is head
3 before = dummy
4 while true:
5 end = before
6 repeat k times:
7 end = end.next
8 if end is none:
9 return dummy.next
10 first = before.next
11 prev = none
12 cur = first
13 repeat k times:
14 next = cur.next
15 cur.next = prev
16 prev = cur
17 cur = next
18 before.next = prev
19 first.next = cur
20 before = first
состояние
before
–
end
–
first
–
prev
–
cur
–
next
–
историянажмите шаг, чтобы вернуться

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

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

  1. end отсчитывает k узлов раньше, чем меняется хоть одна ссылка, поэтому короткий хвост находится, пока он цел, и остаётся как был.
  2. Каждая группа разворачивается циклом с карточки ровно k раз; после него prev — новый первый узел группы, а cur — первый узел за ней.
  3. before.next = prev и first.next = cur пришивают группу обратно, а бывший первый узел, теперь последний, становится before для следующей группы.

Сложность

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

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

Решить на LeetCode ↗

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