Merge Two Sorted Lists

Лёгкая№21фиктивная голова

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

21 Merge Two Sorted ListsРазбор · 1×

Пример: list1 = 3 → 6 → 11 сверху, list2 = 1 → 6 → 8 снизу; каждый узел стоит в колонке своего места в ответе.

nonenonedummy3611168list2list1
ждёт в list1 или list2первый в list1 или list2меньший, берёмtailв ответе

Фиктивный узел: ответ будет висеть на нём, из какого бы списка ни пришёл первый узел

01/33
сначала · назад · пуск · шаг
Скорость
1function mergeTwoLists(list1, list2):
2 dummy = new node
3 tail = dummy
4 while list1 and list2 are not none:
5 if list1.val <= list2.val:
6 tail.next = list1
7 list1 = list1.next
8 else:
9 tail.next = list2
10 list2 = list2.next
11 tail = tail.next
12 tail.next = list1 if list1 is not none else list2
13 return dummy.next
состояние
tail
–
list1
3
list2
1
историянажмите шаг, чтобы вернуться

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

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

  1. Самый маленький из невзятых узлов всегда стоит первым в list1 или list2, поэтому сравнение двух первых выбирает следующий узел ответа.
  2. Фиктивный узел стоит перед ответом, поэтому первый узел добавляется так же, как все остальные. Здесь он пришёл из list2, и отдельная проверка для этого не понадобилась.
  3. Когда один список кончился, другой по-прежнему отсортирован и больше всего взятого: он встаёт целиком, одним действием.

Сложность

Время O(n + m): каждый узел берём один раз. Память O(1): ответ собран из тех же узлов, новый только фиктивный.

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

Решить на LeetCode ↗

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