:orphan:

Merge K Sorted Lists
====================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/merge-k-sorted-lists/

You are given an array of ``k`` linked-lists ``lists``, each linked-list
is sorted in ascending order.

*Merge all the linked-lists into one sorted linked-list and return it.*

 

**Example 1:**

::


   Input: lists = [[1,4,5],[1,3,4],[2,6]]
   Output: [1,1,2,3,4,4,5,6]
   Explanation: The linked-lists are:
   [
     1->4->5,
     1->3->4,
     2->6
   ]
   merging them into one sorted linked list:
   1->1->2->3->4->4->5->6

**Example 2:**

::


   Input: lists = []
   Output: []

**Example 3:**

::


   Input: lists = [[]]
   Output: []

 

**Constraints:**

- ``k == lists.length``
- ``0 <= k <= 10``\ :sup:```4```
- ``0 <= lists[i].length <= 500``
- ``-10``\ :sup:```4```\ ``<= lists[i][j] <= 10``\ :sup:```4```
- ``lists[i]`` is sorted in **ascending order**.
- The sum of ``lists[i].length`` will not exceed ``10``\ :sup:```4```.

.. highlight:: python

Pattern
-------
Linked List, Divide and Conquer, Heap (Priority Queue), Merge Sort

Solution
--------
Same as merge 2 sorted linked lists: pick the smallest head and add it to the
end of the new list.

Code
----

.. literalinclude:: ../problems/hard/merge-k-sorted-lists/merge_k_sorted_lists__approach_1.py
    :language: python
    :lines: 11-

Test
----
>>> from merge_k_sorted_lists__approach_1 import ListNode, merge_k_lists
>>> head1 = ListNode.from_list([1, 5, 6])
>>> head2 = ListNode.from_list([2, 3, 7])
>>> head3 = ListNode.from_list([2, 4, 8])
>>> head = merge_k_lists([head1, head2, head3])
>>> print(head)
1 -> 2 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

Complexity
----------
| :math:`n` is the total number of nodes across all lists, and :math:`k` is the number of lists
| Time: :math:`O(n \log k)` — :math:`O(\log k)` to pop from the heap of size :math:`k` for each of the :math:`n` nodes
| Auxiliary Space: :math:`O(k)` — heap size

.. autoclass:: merge_k_sorted_lists__approach_1.ListNode
   :members:
   :show-inheritance:
   :undoc-members:

.. autofunction:: merge_k_sorted_lists__approach_1.merge_k_lists