## Problem

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 <= 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,4,5],[1,3,4],[2,6]]
[]
[[]]
[[1,2,2],[1,1,2]]
```

## Solution

### Solution 1: Python

```
# 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

```
# 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))`

- Breakup: