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

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param lists ListNode类一维数组 
# @return ListNode类
#

import heapq

class Solution:
    def mergeKLists(self , lists: List[ListNode]) -> ListNode:
        # write code here
        heap = []  # 创建堆

        # 将每个链表的第一个值加入堆，同时将各个链表的头指针往后移动一位
        for i in range(len(lists)):
            if lists[i]:
                heapq.heappush(heap, (lists[i].val, i))
                lists[i] = lists[i].next
        
        dummy_head = ListNode(-1)
        cur = dummy_head

        while heap:
            val, i = heapq.heappop(heap)
            node = ListNode(val)
            cur.next = node
            cur = cur.next
            if lists[i]:
                heapq.heappush(heap, (lists[i].val, i))
                lists[i] = lists[i].next

        return dummy_head.next

思路：使用最小堆来每次pop出每个链表头结点中的最小值

1. 构建最小堆，将所有链表的头结点push到堆中；
2. 只要堆不为空，每次pop出当前堆中的最小值，并加入pop出的这个值所在链表的下一个值

为此，在构建堆时，不仅需要记录值，还需要记录该值来自于那个链表。