---
round: 2
ticket_no: 1
source_no: 20
slug: merge-k-sorted-lists
topic: Linked Lists
difficulty: Hard
leetcode_id: 23
attempted: true
score: 2
verdict: partial
reviewed_at: 2026-09-12
---

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

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

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

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

Ограничения: `k` от 0 до 10^4, длина каждого списка до 500, значения в диапазоне ±10^4, суммарное число элементов не превышает 10^4.

## Ответ

> Так, здесь два принципиальных решения. Вот. Первый — это в том, чтобы мы взяли у каждого списка по первому элементу по голове и положили в одну кучу. Куча, которая организована так, что минимум находится на её вершине. То есть у нас это гарантирует, что у нас в голове куча лежит минимальный элемент, мы его оттуда достаём и кладём в результат, значит, именно значение да, то есть в итоговый список. И из этого элемента берём следующий элемент. То есть он будет указывать на следующий элемент в том списке, откуда он пришёл. Кладем этот элемент в эту кучу. Она снова перебалансируется. Таким образом, мы из неё достаём всегда голову, следующую, пока все из неё не исчерпаем. То есть там всегда ограниченное число элементов в этой куче находится — максимум, сколько всего есть списков. Это первый вариант. Второй вариант строится на слиянии списков. То есть мы берём все списки и попарно их склеиваем. И с первого и второго склеиваем новый список. Он мерч, сортируем, берём минимальные элементы с головы, как бы передвигаем ползуночек. Элемент, который положили, соответственно, он начинает в этом списке уже следующий элемент мы берём. А второй, значит, первый и второй склеили, третий, четвёртый, пятый, шестой. В общем, попарно так склеивали. Потом в полученном списке списков снова попарно склеиваем. И так, пока мы не дойдём до того состояния, что у нас всего один, ну или два списка. Ну, если их три, например, нечетные, значит, ну третьему повезло, он не склеивается, он только в конце пиклеивается. Вот и всё. И в конце у нас получается один список.

## Разбор

**Что верно:** Оба подхода названы и оба корректны. (1) Min-heap: положить головы всех списков в кучу-минимум, на каждом шаге доставать минимум, класть в результат и подкладывать следующий узел из того же списка; размер кучи ≤ k. (2) Divide & conquer: попарное слияние списков по уровням, пока не останется один. Верно отмечено, что берётся именно следующий узел того же списка (связь через `next`), а непустые списки исчерпываются.

**Что упущено и ошибки:** Не названа сложность по времени и памяти ни для одного подхода — это был главный пробел раунда 1, он остался. Не названы граничные случаи: пустой массив списков, списки с пустыми головами (`[[], [1]]`), один список, все списки пустые, отрицательные значения, дубликаты. Формулировка про нечётное число списков («третьему повезло») допустима, но точнее: непарный список сливается на следующем уровне.

**Эталонная идея:** min-heap размера k по головам списков (сравнение по `val`): достать минимум → привязать к результату → подложить `node.next`; либо попарное слияние (divide & conquer) как merge sort на списках.

**Сложность:** время O(N log k), память O(k) для heap или O(log k) для попарного слияния (стек рекурсии).

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

**Разбор задачи:** [`../../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)