题解 | #合并k个已排序的链表#

import heapq

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def mergeKLists(self, lists):
        # 创建一个优先队列
        min_heap = []
        # 初始化，将k个链表的首节点放入优先队列
        for idx, node in enumerate(lists):
            if node:
                heapq.heappush(min_heap, (node.val, idx, node))
        
        # 创建一个哑节点，这将会是合并后链表的头节点的前驱
        dummy = ListNode(0)
        current = dummy
        
        # 当优先队列不为空，循环执行
        while min_heap:
            # 弹出最小元素
            val, idx, node = heapq.heappop(min_heap)
            # 将当前最小节点加入到合并后的链表
            current.next = node
            current = current.next
            # 如果弹出的节点的下一个节点非空，将其加入到优先队列中
            if node.next:
                heapq.heappush(min_heap, (node.next.val, idx, node.next))
        
        # 返回合并后的链表的头节点
        return dummy.next