061-力扣刷题-23--合并K个排序链表

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

示例:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

from heapq import heapify,heappop #从堆模块导入建堆的函数heapify以及弹出模块heappop
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        #读取所有节点的值
 #       if lists is None:
   #         return None #这里会出现[[]] 不通过
        h = [] 
        for node in lists:
            while node:
                h.append(node.val)
                node = node.next
        # 构造一个最小堆
        if not h:
            return None
        heapify(h) #转换成最小堆
        # 构造链表
        root = ListNode(heappop(h)) #弹出第一个最小值作为头节点
        curnode = root
        while h:
            nextnode = ListNode(heappop(h)) #建立新的节点
            curnode.next = nextnode #指向下一个节点
            curnode = nextnode #指针后移

        return root