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

4. Слияние двух отсортированных списков без копирования

Лёгкая

Даны головы двух односвязных списков, оба отсортированы по возрастанию val. Слейте их в один отсортированный список и верните его голову.

Новые узлы создавать нельзя — переставляйте ссылки next у существующих. Проверка это отслеживает.

В работе: Склеить две очереди задач, каждая уже упорядочена по времени, без копирования объектов задач.

Пример 1

Ввод
l1 = 1 → 3 → 5
l2 = 2 → 4
Вывод
1 → 2 → 3 → 4 → 5

В тестах списки записаны массивами, в функцию приходят узлы.

Пример 2

Ввод
l1 = пусто
l2 = 7
Вывод
7

Ограничения

  • 0 ≤ длина каждого списка ≤ 50 000 (в JavaScript — до 300 000)
  • Рекурсия на 50 000 узлов упрётся в предел глубины Python
  • Лимит — 1 с на тест.
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. Класс ListNode уже объявлен: у узла есть поля val и next. Пустой список — None (в JS — null). 
def merge(l1: ListNode | None, l2: ListNode | None) -> ListNode | None:
Связный списокДва указателяцельO(n)

Источник: отчёт о Яндексе, 2022. Условие пересказано своими словами.

Давали на собеседовании? Ответов пока мало — ваш поможет.