Day 24 - Merge k Sorted Lists
Tags: leetcode, python, challenge
Published: 2021-01-24 13:43:24

>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 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^4`
* `0 <= lists[i].length <= 500`
* `-10^4 <= lists[i][j] <= 10^4`
* `lists[I]` is sorted in __ascending order__.
* The sum of `lists[i].length` won't exceed `10^4`.

## Tests

```python
import pytest
from .util import toListNode, toList
from .Day24_MergeKSortedLists import Solution

s = Solution()


@pytest.mark.parametrize(
    "lists,expected",
    [([[1, 4, 5], [1, 3, 4], [2, 6]], [1, 1, 2, 3, 4, 4, 5, 6]), ([], []), ([[]], [])],
)
def test_merge_k_lists(lists, expected):
    assert toList(s.mergeKLists(list(map(lambda x: toListNode(x), lists)))) == expected

@pytest.mark.parametrize(
    "lists,expected",
    [([[1, 4, 5], [1, 3, 4], [2, 6]], [1, 1, 2, 3, 4, 4, 5, 6]), ([], []), ([[]], [])],
)
def test_merge_k_lists2(lists, expected):
    assert toList(s.mergeKLists2(list(map(lambda x: toListNode(x), lists)))) == expected
```

## Solution

```python
from typing import List
from .util import ListNode
from queue import PriorityQueue


def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    head = ListNode()
    current = head
    while l1 and l2:
        if l1.val <= l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l1
            l1 = current.next.next
        current = current.next
    current.next = l2 if l2 else l1
    return head.next


class Solution:
    def build_queue(self, lists: List[ListNode]) -> PriorityQueue:
        q = PriorityQueue()
        for l in lists:
            if l:
                q.put((l.val, l))
        return q

    def mergeKLists2(self, lists: List[ListNode]) -> ListNode:
        head = ListNode()
        current = head
        q = self.build_queue(lists)

        while not q.empty():
            val, list_node = q.get()
            current.next = ListNode(val)
            current = current.next
            next_node = list_node.next
            if next_node:
                q.put((next_node.val, next_node))

        return head.next

    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        k = len(lists)
        if k == 0:
            return None

        step = 1
        while step < k:
            for i in range(0, k - step, step * 2):
                lists[i] = mergeTwoLists(lists[i], lists[i + step])
            step *= 2

        return lists[0]

```

## Analysis

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/e78quzr46qk6byepyb4u.png)


## Commentary

[Link to code](https://github.com/ruarfff/leetcode-jan-2021)

This seemed like a good place to use a [PriorityQueue](https://docs.python.org/3/library/queue.html#queue.PriorityQueue) to me but I couldn't get it to work in leetcode as the ListNode class did not implement `__gt__`or `__lt__`. I have left an example in the code called `mergeKLists2`.

The solution I went with was kind of cheating. I more or less copied the solution from [Day 4](https://dev.to/ruarfff/day-4-merge-two-sorted-lists-4fed). I improved it a little but basically we are breaking the problem down into merging 2 sorted lists. 

We merge in steps to basically merge in pairs. Eventually you get all lists merged. 

The runtime is about `O(n log k)` where k = `len(lists)`. We don't use up any extra space.