# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
n = len(lists)
pq = [(lists[i].val, count, lists[i]) for count, i in enumerate(range(n)) if lists[i]] # 排除空数组
heapq.heapify(pq)
index = n # 使用index表示结点被发现的顺序, 因为相同值结点的先后顺序不重要, 因此加入一个递增的数值, 避免比较涉及到结点(无法比较)
root, node = None, None
while pq:
_, _, t_node = heapq.heappop(pq)
if root is None:
root = t_node
node = t_node
else:
node.next = t_node
node = t_node
if t_node.next is not None:
next_node = t_node.next
heapq.heappush(pq, (next_node.val, index, next_node))
index += 1
return root