# Билет 05 — рабочий лист

## Условие

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

## Решение — пиши здесь

```ruby
#
# Твоя реализация. Не забудь: проговаривай (пиши в комментариях) —
# 1) идею, 2) сложность по времени, 3) сложность по памяти,
# 4) граничные случаи.
#
# Определение узла списка уже дано:
# class ListNode
#   attr_accessor :val, :next
#   def initialize(val = 0, _next = nil)
#     @val = val
#     @next = _next
#   end
# end
#

def merge_k_lists(lists)
  # Тут представим, что у нас есть реализован класс "Куча", который держит на вершине минимальные элементы, в которые можно передать, например, метод для получения значения, по которому будет идти сравнение. Вероятно, более корректно было бы сделать компаратор, да? Давай попробуем его сделать.
  heads = MinHeap.new(->(a, b) { a.val <=> b.val })

  head = nil
  tail = nil
  lists.each { |list| heads.push(list) unless list.nil? }


  until heads.empty?
    el = heads.pop

    if head.nil?
      head = ListNode.new(el.val)
      tail = head
    else
      tail.next = ListNode.new(el.val)
      tail = tail.next
    end

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

  head
end
```

run O(n log k) 

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