合并K个排序链表

【题目】：合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6

【算法思想】:将每条链表中的每个元素值提取出来，构成一个最小值堆，然后弹出每一个元素，将其放入新的链表。
【算法实现python3】

# 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:
        def heap(lists:List[ListNode])-> ListNode:
            import heapq
            bh=[]
            n=len(lists)
            for i in range(n):
                while lists[i]:
                    bh.append(lists[i].val)
                    lists[i]=lists[i].next
            heapify(bh)
            dummy=ListNode(None)
            res=dummy#dummy的地址给了res
            while bh:
                res.next=ListNode(heappop(bh))
                res=res.next
            return dummy.next#如果返回res,由于res=res.next,所以最后返回只有一个。所以，返回的是dummy.next。
        return heap(lists)

【时间复杂度】
O(nlgn)

本文地址：https://blog.csdn.net/Baoweijie12/article/details/107350164