---
round: 3
ticket_no: 31
source_no: 20
slug: merge-k-sorted-lists
topic: Linked Lists
difficulty: Hard
leetcode_id: 23
attempted: true
score:
verdict:
reviewed_at:
---

# Билет 31 — Merge K Sorted Lists

## Условие (как предъявлено)

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

```
Input:  lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
```

Constraints: `k == lists.length`; `0 <= k <= 10^4`; `0 <= lists[i].length <= 500`; `-10^4 <= lists[i][j] <= 10^4`; суммарное число узлов во всех списках не превышает `10^4`.

## Ответ

> Значит, здесь нам поможет структура куча, в которой на верхушке будет минимальный элемент. Вот мы, получается, заполняем её самыми первыми элементами списков. Это минимальные элементы из них. Она сформирована из минимальных элементов каждого списка. Дальше мы берём из кучи его голову, это как раз и будет наш первый элемент в результирующем массиве. Дальше мы у этого элемента спрашиваем, какой-то следующий элемент. Соответственно, он указывает на следующий элемент в соответствующем списке. И добавляем его в кучу: куча перестраивается, и мы снова берём оттуда голову. Ну, соответственно, если у элемента, которого мы выкидываем, нету продолжения, то мы это продолжение. Ну, как бы, всё это, да, у нас куча уменьшилась, она содержит уже элементы двух списков. Только есть альтернативное решение без кучи — есть с помощью сортировок мержем всех этих массивов, но их надо проводить аккуратно, то есть нужно попарно их мержить и до тех пор, пока число их не уменьшится до одного. Вот. Ну, тут нарная память потребляется — алгоритмически тут сложнее. Хорошо, когда у нас есть готовая куча.

## Разбор

**Что верно:**

**Что упущено и ошибки:**

**Эталонная идея:**

**Время:** O(...) — что доминирует

**Память:** O(...) дополнительная (+ O(...) на выход / стек рекурсии)

**Граничные случаи:** 1) ... 2) ... 3) ...

**Критерии:** идея ⚠️ · структура данных ⚠️ · сложность ⚠️ · граничные случаи ⚠️

**Канон сложности:** сверить с [`../complexity-cheat-sheet.md`](../complexity-cheat-sheet.md) (таблица по 32 задачам)

**Разбор задачи:** [`../../algo-solutions/02-extra/01-linked-lists/20-merge-k-sorted-lists.md`](../../algo-solutions/02-extra/01-linked-lists/20-merge-k-sorted-lists.md)