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

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

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

Дан массив из `k` отсортированных связных списков. Нужно слить их в один отсортированный связный список.

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

## Ответ

> Идея такая. Мы берем по младшему, то есть у нас должен быть список указателей на самые первые элементы в каждом списке. Мы берем эти все элементы. Первый я из каждого списка сравниваем. Какой из них минимальный? Добавляем его в итоговый список. Дальше. Из которого списка мы взяли, мы там передвигаем этот ползуночек. То есть теперь он на второй элемент смотрим. Теперь снова сравниваем элементы, на который указывают указатели. Берем снова минимальный. Ну, если равны, тогда без разницы какой. Добавляем в итоговый список и так далее. Если из списка уже нечего взять, ну значит, его уже не учитываем и добираем из оставшихся.

## Разбор

**Что верно:** схема слияния k указателей верная: держим указатель на голову каждого списка, на каждом шаге берём минимальный и продвигаем только его список, опустевшие списки исключаем.

**Что упущено и ошибки:** не найден ключевой приём задачи: линейный поиск минимума даёт O(N·k), тогда как Hard-задача просит O(N log k) — min-heap по головам или попарное слияние (divide & conquer). В Ruby кучи в stdlib нет, поэтому попарное слияние практичнее. Сложность не названа, граничные случаи не разобраны.

**Эталонная идея:** min-heap размера k: положить головы, вынуть минимум, подложить следующий из того же списка — O(N log k); либо рекурсивное слияние пар списков, как в merge sort.

**Сложность:** время O(N log k), память O(k) для кучи или 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)