Войти Регистрация
Алгоритмы

151. Развернуть партии посылок на ленте

Средняя

Лента сортировочного центра описана односвязным списком: val узла — номер посылки, узел со значением 0 — разделитель партий.

Партии грузили в машину задом наперёд, поэтому порядок внутри каждой партии нужно развернуть. Разделители остаются на своих местах, порядок партий не меняется.

Переставляйте ссылки next у существующих узлов, новые узлы не создавайте. Верните голову списка.

В работе: Выгрузка на ПВЗ Wildberries: машина пришла, партии внутри перевёрнуты, а сканер ждёт исходный порядок.

Пример 1

Ввод
head = [3, 1, 2, 0, 5, 4, 0, 0, 7]
Вывод
[2, 1, 3, 0, 4, 5, 0, 0, 7]

Партии 3 1 2, 5 4, пустая, 7 → 2 1 3, 4 5, пустая, 7.

Пример 2

Ввод
head = [0, 8, 9]
Вывод
[0, 9, 8]

Разделитель в начале, за ним одна партия.

Ограничения

  • 0 ≤ длина списка ≤ 10⁵ (в JavaScript — до 10⁶)
  • 0 ≤ val ≤ 10⁶
  • Рекурсия на 10⁵ узлов упрётся в предел глубины Python
  • Лимит — 2 с на тест (1500 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. Класс ListNode уже объявлен: у узла есть поля val и next. Пустой список — None (в JS — null). 
def reverse_batches(head):
Связный списокРазворот спискацельO(n)

Источник: наша задача на данных Wildberries. Условие пересказано своими словами.