---
title: Merge K Sorted Lists
difficulty: Hard
category: Heap (Priority Queue), Divide and Conquer
leetcode_id: 23
revision_count: 2
last_revision: 2026-09-12
---

# Merge K Sorted Lists

> **LeetCode:** [#23](https://leetcode.com/problems/merge-k-sorted-lists/)
> **Сложность:** Hard
> **Категория:** Heap / Divide and Conquer

## Условие

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

## Ключевая идея

Два подхода. **Min-heap:** кладём головы всех списков в кучу, на каждом шаге забираем минимальный элемент, подкладываем следующий из того же списка. **Divide and Conquer:** сливаем списки попарно рекурсивно — как merge sort, но на списках.

## Оценка сложности

| Подход | Время | Память |
|--------|-------|--------|
| Min-heap | O(N log k) | O(k) |
| Divide and Conquer | O(N log k) | O(log k) (стек рекурсии) |

**N** — общее количество элементов во всех списках, **k** — количество списков.

## Решение (Ruby)

### Min-heap (binary heap)

```ruby
# Определение ListNode дано в LeetCode:
# class ListNode
#   attr_accessor :val, :next
#   def initialize(val = 0, _next = nil)
#     @val, @next = val, _next
#   end
# end

class MinHeap
  def initialize
    @heap = []
  end

  def push(node)
    @heap << node
    sift_up(@heap.size - 1)
  end

  def pop
    return nil if @heap.empty?
    min = @heap[0]
    last = @heap.pop
    if @heap.any?
      @heap[0] = last
      sift_down(0)
    end
    min
  end

  def empty? = @heap.empty?

  private

  def sift_up(idx)
    while idx > 0
      parent = (idx - 1) / 2
      break if @heap[parent].val <= @heap[idx].val
      @heap[parent], @heap[idx] = @heap[idx], @heap[parent]
      idx = parent
    end
  end

  def sift_down(idx)
    size = @heap.size
    loop do
      smallest = idx
      left = 2 * idx + 1
      right = 2 * idx + 2
      smallest = left if left < size && @heap[left].val < @heap[smallest].val
      smallest = right if right < size && @heap[right].val < @heap[smallest].val
      break if smallest == idx
      @heap[idx], @heap[smallest] = @heap[smallest], @heap[idx]
      idx = smallest
    end
  end
end

# @param {ListNode[]} lists
# @return {ListNode}
def merge_k_lists(lists)
  heap = MinHeap.new

  lists.each do |list|
    heap.push(list) if list
  end

  dummy = ListNode.new
  current = dummy

  until heap.empty?
    node = heap.pop
    current.next = node
    current = current.next
    heap.push(node.next) if node.next
  end

  dummy.next
end
```

### Divide and Conquer (рекурсивное слияние пар)

```ruby
# @param {ListNode[]} lists
# @return {ListNode}
def merge_k_lists(lists)
  merge_range(lists, 0, lists.size - 1)
end

def merge_range(lists, l, r)
  return nil if l > r
  return lists[l] if l == r

  mid = (l + r) / 2
  left = merge_range(lists, l, mid)
  right = merge_range(lists, mid + 1, r)
  merge_two(left, right)
end

def merge_two(l1, l2)
  dummy = ListNode.new
  cur = dummy

  while l1 && l2
    if l1.val < l2.val
      cur.next = l1
      l1 = l1.next
    else
      cur.next = l2
      l2 = l2.next
    end
    cur = cur.next
  end

  cur.next = l1 || l2
  dummy.next
end
```

## Разбор на примере (min-heap)

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

Heap: [1 (list0), 1 (list1), 2 (list2)]

Шаг 1: pop 1 (list0) → result: 1 → push 4 (list0)
  Heap: [1 (list1), 4 (list0), 2 (list2)]
Шаг 2: pop 1 (list1) → result: 1 → push 3 (list1)
  Heap: [2 (list2), 4 (list0), 3 (list1)]
Шаг 3: pop 2 (list2) → result: 2 → push 6 (list2)
  Heap: [3 (list1), 4 (list0), 6 (list2)]
Шаг 4: pop 3 (list1) → result: 3 → push 4 (list1)
  Heap: [4 (list0), 4 (list1), 6 (list2)]
Шаг 5: pop 4 (list0) → result: 4 → push 5 (list0)
  Heap: [4 (list1), 5 (list0), 6 (list2)]
Шаг 6: pop 4 (list1) → ничего не пушим (list1 закончился)
  Heap: [5 (list0), 6 (list2)]
Шаг 7: pop 5 (list0) → ничего не пушим (list0 закончился)
  Heap: [6 (list2)]
Шаг 8: pop 6 (list2) → ничего не пушим (list2 закончился)
  Heap: []

Result: 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6
```

## Edge Cases

- **Пустой массив**: `lists = []` → `nil`.
- **Массив с пустыми списками**: `lists = [[], [1]]` → игнорируем nil-головы при инициализации heap.
- **Один список**: `lists = [[1, 2, 3]]` → возвращаем его как есть (heap с одним элементом).
- **Все списки пусты**: `lists = [[], []]` → `nil`.
- **Отрицательные числа**: алгоритм корректен, min-heap работает с любыми `Comparable`.
- **Дубликаты**: корректно обрабатываются (в heap хранятся узлы, при равных val порядок неважен).

## Типичные ошибки

1. ❌ **Забыть проверить `list` на nil перед push** — в heap нельзя класть nil.
2. ❌ **Не обновлять `current.next` при pop** — забыть привязать вытащенный узел к результату.
3. ❌ **Heap с val вместо узлов** — если хранить только val, теряется связь со списком; нельзя подложить следующий элемент.
4. ❌ **Divide and Conquer: забыть базовый случай** — `l > r` (nil) и `l == r` (один список).
5. ❌ **Создавать новые узлы** — задача просит перелинковать существующие, не создавать новые.

## Альтернативные подходы

| Подход | Время | Память | Комментарий |
|--------|-------|--------|-------------|
| Collect + sort + rebuild | O(N log N) | O(N) | Собрать все val в массив, отсортировать, создать новые узлы. Просто, но неоптимально. |
| **Min-heap** | **O(N log k)** | **O(k)** | **финальное решение** — классика для интервью |
| Divide and Conquer | O(N log k) | O(log k) | Без доп. памяти (кроме стека рекурсии). На практике чуть медленнее heap. |

Divide and Conquer на словах проще (нет структур данных), а heap — де-факто стандарт для этой задачи на интервью. Оба — O(N log k), но heap даёт строчку «priority queue» в резюме.

## Заметки после повторения

_— Заполняется после каждой тренировки._