Merge k Sorted Lists

Сложная№23слияние k списков

Даны k связных списков, каждый отсортирован по возрастанию; какие-то могут быть пустыми. Нужно соединить все их узлы в один отсортированный связный список и вернуть его голову. Наш пример: 2 → 6, пустой список, 1 → 4 → 7, 3 → 5 — ответ 1 → 2 → 3 → 4 → 5 → 6 → 7.

23 Merge k Sorted ListsРазбор · 1×

Пример: 2 → 6, пустой список, 1 → 4 → 7, 3 → 5. Слева — списки, ниже — куча и ответ, который растёт после узла dummy.

lists[0]none26lists[1]nonelists[2]none147lists[3]none35кучаменьшее слева—
ещё не дошлив кучеnode, только что досталиуже в ответе

В куче будет по одному узлу от каждого списка, по node.val

01/55
сначала · назад · пуск · шаг
Скорость
1function mergeKLists(lists):
2 heap = empty min-heap // ordered by node.val
3 for each head in lists:
4 if head is not none:
5 push head into heap
6 dummy = new node
7 tail = dummy
8 while heap is not empty:
9 node = pop min from heap
10 tail.next = node
11 tail = node
12 if node.next is not none:
13 push node.next into heap
14 return dummy.next
состояние
heap
[]
head
–
node
–
tail
–
историянажмите шаг, чтобы вернуться

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

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

  1. Каждый список отсортирован, поэтому наименьший ещё не привязанный узел — всегда первый неиспользованный узел какого-то списка. В куче лежат ровно такие, по одному на список, поэтому наверху следующий узел ответа.
  2. У пустого списка нет головы, и он не попадает в кучу; закончившийся список ничего не кладёт, и куча просто уменьшается. Ни то ни другое не требует особого случая дальше.
  3. Фиктивный узел dummy позволяет привязать первый узел так же, как остальные, поэтому tail.next = node — одна строка на все случаи; узлы перевязываются, а не копируются.

Сложность

Время O(N log k) для N узлов в k списках: каждый узел один раз попадает в кучу не больше чем из k и один раз её покидает. Память O(k) на кучу: ответ собран из тех же узлов.

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

Решить на LeetCode ↗

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