problem address
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Example: Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6 之前有两两合并链表，多次合并不就可以了使用堆 (1). 读取所有链表的值 (2). 构造一个最小堆heapq实现 (3). 根据最小堆构造一个链表 # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None from heapq import heapify, heappop class Solution(object): def mergeKLists(self, lists): """ :type lists: List[ListNode] :rtype: ListNode """ # 读取所有节点值 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