Ctrl K

Слияние многих отсортированных цепочек

Сложная
Дан массив chains из первых узлов нескольких односвязных списков. Значения в каждом списке идут по неубыванию; пустой список задан как None. Сам массив тоже может быть пустым. Соедините узлы всех списков в один список, упорядоченный по неубыванию, и верните его первый узел (или None, если узлов нет). Списков может быть много, поэтому попарное слияние по очереди может оказаться слишком медленным.
Пример 1
chains=[list_node([3, 7, 9]), list_node([-2, 7]), list_node([0, 4, 11, 12])] → [-2, 0, 3, 4, 7, 7, 9, 11, 12]

Все узлы трёх списков выстраиваются по неубыванию: -2, 0, 3, 4, 7, 7, 9, 11, 12.

Пример 2
chains=[list_node([]), list_node([5]), list_node([])] → [5]

Два списка пусты, в ответе остаётся единственный узел 5.

Пример 3
chains=[] → None
Ограничения
  • 0 ≤ len(chains) ≤ 10⁴
  • В каждом списке от 0 до 500 узлов
  • Всего узлов не больше 10⁵
  • -10⁴ ≤ Node.val ≤ 10⁴
  • Каждый список отсортирован по неубыванию
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиСортировка связного списка СредняяСортировка своими руками СредняяКонтур городской застройки СложнаяМеньшие справа СложнаяСуммы отрезков в заданной полосе Сложная
загружаем Python…
Вход
chains=[list_node([3, 7, 9]), list_node([-2, 7]), list_node([0, 4, 11, 12])]
Ожидается
[-2, 0, 3, 4, 7, 7, 9, 11, 12]

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 6 тестов на сервере, включая скрытые.