Rotate List

Средняя№61на расстоянии n

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

61 Rotate ListРазбор · 1×

Пример: повернуть 3 → 8 → 1 → 6 → 4 вправо k = 7 раз: поворотов больше, чем узлов.

none38164head
node, считаемslowfastповёрнутый список

head — 3, не none: список не пуст

01/37
сначала · назад · пуск · шаг
Скорость
1function rotateRight(head, k):
2 if head is none:
3 return none
4 length = 0
5 node = head
6 while node is not none:
7 length = length + 1
8 node = node.next
9 k = k mod length
10 fast = head
11 slow = head
12 repeat k times:
13 fast = fast.next
14 while fast.next is not none:
15 slow = slow.next
16 fast = fast.next
17 fast.next = head
18 head = slow.next
19 slow.next = none
20 return head
состояние
head
3
k
7
length
–
node
–
fast
–
slow
–
историянажмите шаг, чтобы вернуться

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

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

  1. Каждые length поворотов возвращают список в исходный вид, поэтому важны только k mod length поворотов. k может быть намного больше списка, поэтому сначала считаем длину.
  2. Поворот на k переносит последние k узлов в начало. fast уходит на k узлов вперёд, и когда он на хвосте, slow стоит прямо перед этими k узлами: после него и режем.
  3. Поворот делают три ссылки: хвост на старую голову, head на slow.next, slow.next на none. При k mod length = 0 slow останавливается на хвосте, и те же три ссылки возвращают список без изменений.

Сложность

Время O(n): один проход, чтобы посчитать, и ещё один проход fast по списку; после mod само k не важно. Память O(1): несколько указателей, узлы перецепляются, а не копируются.

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

Решить на LeetCode ↗

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