## Problem Statement

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

Example 1:

 `````` 1 2 3 4 5 6 7 8 9 10 `````` ``````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:

 ``````1 2 `````` ``````Input: lists = [] Output: [] ``````

Example 3:

 ``````1 2 `````` ``````Input: lists = [[]] Output: [] ``````

### Constraints:

• `k == lists.length`
• `0 <= k <= 104`
• `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` will not exceed `10^4`.

### Test Cases

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

See the problem

## Solution

### Solution 1: Python

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 `````` ``````# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next import heapq class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: ans = node = ListNode() hp = list() continue_run = True remove_none = False count = 0 while continue_run: if len(lists): for i, l in enumerate(lists): if l: heapq.heappush(hp, (l.val, count, l)) lists[i] = l.next count += 1 else: remove_none = True if remove_none: lists = [x for x in lists if x is not None] remove_none = False if len(hp): (_, _, node.next) = heapq.heappop(hp) node = node.next else: continue_run = False return ans.next ``````

### Solution 2: Python

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 `````` ``````# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next import heapq class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: ans = node = ListNode() hp = list() count = 0 for l in lists: if l: heapq.heappush(hp, (l.val, count, l)) count += 1 while len(hp): (_, _, l) = heapq.heappop(hp) if l.next: heapq.heappush(hp, (l.next.val, count, l.next)) count += 1 node.next = l node = l return ans.next ``````

Here,

• I use `count` as a second member for comparison for case when tuples has same `l.val`

• I could have used list indices as second member but they could also conflict.
• Because `count` will always be unique
• Time complexity is `O(nlogk)`

• Breakup: `O(klogk + n+ (n-k)logk))`