round: 4
ticket_no: 05
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-15
---

# Билет 05 — Merge k Sorted Lists

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

Дан массив `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: []
```

Constraints: `k = lists.length`, `0 <= k <= 10^4`; каждый список: `0 <= length <= 500`; значения: `-10^4 <= lists[i][j] <= 10^4`. Сумма длин ≤ 10^4.

## Ответ

> Дословно из `work-05-merge-k-sorted-lists.md` (код как написан):

```ruby
def merge_k_lists(lists)
  heads = MinHeap.new(->(a, b) { a.val <==> b.val })

  result = []
  lists.each { |list| heads.push list }

  until heads.empty?
    el = heads.pop

    result << el

    heads.push(el.next) if el.next
  end

  result
end

# run O(n x k)
# mem: O(k) - Считаем только дополнительные расходы, результат, как память, не считаем.
```

## Разбор

**Что верно:**
- Идея каноническая: min-heap с головами списков → pop минимума → подложить `el.next`; цепочка результата собирается через head/tail (попытка пересдачи), а не плоским массивом. ✅
- Память O(k) auxiliary — верно (куча до k элементов). ✅

**Ошибки (финальная версия пересдачи):**
1. ❌ **SyntaxError: `a.val <==> b.val`.** В Ruby spaceship-оператор — `<=>`, а не `<==>` (лишний `=`). Код не компилируется вообще (`unexpected '=>'`). Ошибка была в ОБЕИХ версиях; при первом разборе не отловлена — проверка синтаксиса обязательна.
2. ❌ **`list.first` / `list.empty?`** — вход `lists` — массив голов `ListNode`, у узла нет этих методов. Правильно: `heads.push(list) if list`.
3. ❌ **`head.empty?`** — NoMethodError (у `ListNode`/`nil` нет `empty?`). Правильно: `if head.nil?`.
4. ⚠️ **Куча не реализована** — декларирована «представим, что есть»; в Ruby нет кучи в stdlib.
5. ❌ **Сложность O(n×k)** — с кучей O(N log k).
6. ⚠️ Edge cases не названы.

## Пересдача (попытка 3) — не удалась

Исправлено: spaceship `<=>` (был SyntaxError `<==>`), вход обрабатывается как узлы (`push(list) unless list.nil?`), сложность O(N log k).

Осталось два фатальных бага:
1. `if head.empty?` → NoMethodError на nil-голове (должно `head.nil?`).
2. `tail` не двигается в else-ветке → `tail.next` перезаписывается, цепочка не растёт: `[[1,4,5],[1,3,4],[2,6]]` → `[1,6]` вместо 8 узлов. Нужно `tail = tail.next` после пришивания.

С обоими фиксами — 7/7 тестов OK. Урок: при построении связного списка из кучи каждый pop обязан двигать `tail`; проверка `empty?` — только для структур данных, не для узлов/nil.

**Что упущено и ошибки:**
1. ❌ **Тип результата — массив, а не связный список.** Условие требует вернуть голову `ListNode`. `result << el` собирает плоский массив узлов с сохранёнными исходными `next`-связями — merged-цепочка не пересобрана. Нужен dummy-узел: `dummy.next = el; tail = tail.next`, в конце `dummy.next`.
2. ❌ **Пустые списки не отфильтрованы — падение на примере условия.** `lists = [[]]` → `push(nil)` → `el = nil` → `el.next` → NoMethodError. Нужно `lists.each { |l| heads.push(l) if l }`. То же для всего-пустого входа.
3. ⚠️ **Куча не реализована.** «Представим, что есть класс Куча» — план верный, но в Ruby нет кучи в stdlib; на интервью нужно быть готовым реализовать push/pop/empty на массиве (бинарная куча на O(log k) на операцию) либо выбрать подход без кучи.
4. ❌ **Сложность O(n×k) неверно.** С кучей — **O(N log k)** (N — суммарное число узлов, k — число списков, каждая операция кучи O(log k)). O(n·k) — это линейный поиск минимума по всем головам на каждом шаге, не кучный.

**Эталонная идея:**
Куча из k голов. Пока не пуста: pop минимум → пришить к хвосту результата → подложить следующий узел того же списка. Ноль и пустые списки отфильтровать на старте. Аналог: divide-and-conquer попарного слияния (как merge sort) — та же сложность O(N log k), память O(log k) стеком.

**Время:** O(N log k) — N pop/push'ей по O(log k).

**Память:** O(k) auxiliary (куча) + O(N) на выходной список.

**Граничные случаи:** 1) `lists = []` и `lists = [[]]` → `nil` (не падать на nil-головах); 2) один список → вернуть его как есть; 3) все списки пустые → `nil`; 4) одинаковые значения в разных списках — стабильность неважна, порядок любой; 5) `k = 10^4` списков.

**Критерии:** идея ✅ · структура данных ⚠️ (куча декларирована, не реализована) · сложность ❌ (O(n×k) вместо O(N log k), память O(k) верно) · граничные случаи ❌ · код падает на примере условия → failed.

**Канон сложности:** O(N log k) / O(k) — сверить с `complexity-cheat-sheet.md`.

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