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

使用小顶堆的方式找出最小val值的节点

这里使用heapq这个轻量化的类，运行效率更快

——步骤一: 将lists列表中的元素push到小顶堆中

——步骤二：将小顶堆的堆顶元素弹出，这个就是我们要的最小值

——步骤三：判断链表后续是否还有节点，有的话push到小顶堆中

import heapq
from typing import List

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        # 小顶堆：存储 (val, index, node)，但其实不需要 node，只需 index 来追踪
        heap = []
        # 初始化堆：把每个非空链表的头节点加入
        for i, node in enumerate(lists):
            if node:
                heapq.heappush(heap, (node.val, i, node))

        dummy = ListNode(-1)
        p = dummy

        while heap:
            val, idx, node = heapq.heappop(heap)
            p.next = node
            p = p.next
            # 如果该链表还有下一个节点，加入堆
            if node.next:
                heapq.heappush(heap, (node.next.val, idx, node.next))

        return dummy.next