23. 合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2：

输入：lists = []
输出：[]
示例 3：

输入：lists = [[]]
输出：[]
 

思路：优先队列

T：O（n）

 1 # Definition for singly-linked list.
 2 # class ListNode:
 3 #     def __init__(self, val=0, next=None):
 4 #         self.val = val
 5 #         self.next = next
 6 class Solution:
 7     def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
 8         import heapq 
 9         dummy = ListNode(0)
10         p = dummy 
11         h = []
12         for i in range(len(lists)):
13             if lists[i]:
14                 heapq.heappush(h, (lists[i].val, i))
15                 lists[i] = lists[i].next 
16         while h:
17             val, idx = heapq.heappop(h)
18             p.next = ListNode(val)
19             p = p.next 
20             if lists[idx]:
21                 heapq.heappush(h, (lists[idx].val, idx))
22                 lists[idx] = lists[idx].next 
23         return dummy.next