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

152. Плейлист: новинка, потом классика

Средняя

Подборка в МТС Музыке хранится односвязным списком треков, отсортированным от свежих к старым: t₀ → t₁ → … → tₙ₋₁.

Нужен порядок «новинка, потом классика»: t₀ → tₙ₋₁ → t₁ → tₙ₋₂ → ….

Переставьте ссылки next у существующих узлов за O(1) дополнительной памяти и верните голову.

В работе: Режим «Микс» в подборке МТС Музыки: слушатель не устаёт от одних новинок и не скучает на старых треках.

Пример 1

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

1, 5, 2, 4, 3.

Пример 2

Ввод
head = [10, 20, 30, 40]
Вывод
[10, 40, 20, 30]

10, 40, 20, 30.

Ограничения

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

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