LeetCode 23. Merge k Sorted Lists–C++,Python解法–优先队列，分治法
LeetCode题解专栏：LeetCode题解 LeetCode 所有题目总结：LeetCode 所有题目总结 大部分题目C++，Python，Java的解法都有。
题目地址：Merge k Sorted Lists - LeetCode
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这道题目是经典的对K个有序链表进行合并，可以使用最小堆或者说优先队列。
如果采用暴力的方法，也就是把所有节点加入数组，排序，那么时间复杂度是O(NlogN)。
采用最小堆的时间复杂度是O(NlogK)。
Python解法如下：
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None from queue import PriorityQueue class Solution: def mergeKLists(self, lists: list) -> ListNode: dummy = ListNode(None) curr = dummy q = PriorityQueue() for node in lists: if node: q.put((node.val,id(node),node)) while q.qsize()>0: curr.next = q.get()[2] curr=curr.next if curr.next: q.put((curr.next.val,id(curr.next), curr.next)) return dummy.next如果采用分治法，时间复杂度相同。
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None from queue import PriorityQueue class Solution: def mergeKLists(self, lists: List[ListNode]) -> ListNode: amount = len(lists) interval = 1 while interval < amount: for i in range(0, amount - interval, interval * 2): lists[i] = self.merge2Lists(lists[i], lists[i + interval]) interval *= 2 return lists[0] if amount > 0 else lists def merge2Lists(self, l1, l2): head = point = ListNode(0) while l1 and l2: if l1.val <= l2.val: point.next = l1 l1 = l1.next else: point.next = l2 l2 = l1 l1 = point.next.next point = point.next if not l1: point.next=l2 else: point.next=l1 return head.next