23.Merge k Sorted Lists
===
###### tags: `Hard`,`Linked List`,`Heap`,`Divide and Conquer`
[23. Merge k Sorted Lists](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 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` will not exceed 10^4^.
### 解答
#### Python
```python=
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
def merge2Lists(l1, l2):
head = ListNode()
cur = head
while l1 and l2:
if l1.val <= l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
if l1: cur.next = l1
else: cur.next = l2
return head.next
N = len(lists)
if N <= 0: return None
step = 1
while step < N:
for i in range(0, N - step, step*2):
lists[i] = merge2Lists(lists[i], lists[i + step])
step *= 2
return lists[0]
```
> [name=Yen-Chi Chen][time=Sun, Mar 12, 2023]
### Reference
[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)