leetcode--合并K个排序链表

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

示例:

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

# Definition for singly-linked list.# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneimport heapqclass Solution:    def mergeKLists(self, lists: List[ListNode]) -> ListNode:        h = []        for node in lists:            while node:                h.append(node.val)                node = node.next        if not h:            return None        heapq.heapify(h) #转换成最小堆        # 构造链表        root = ListNode(heapq.heappop(h))        curnode = root        while h:            nextnode = ListNode(heapq.heappop(h))            curnode.next = nextnode            curnode = nextnode        return root

执行用时 : 104 ms, 在Merge k Sorted Lists的Python3提交中击败了77.24% 的用户

内存消耗 : 17.2 MB, 在Merge k Sorted Lists的Python3提交中击败了42.33% 的用户