Leetcode第二十三题：合并K个排序链表

题目：

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

示例:

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/merge-k-sorted-lists 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

个人思路：

2个合并成1个后再与下一个比，见21题，或者用败者树？

官方答案推荐：

①优先级队列：各链表队头元素入队，python使用heapq即堆

②分治法：图来自leetcode官方答案，节省时间。

 

python代码：

#优先级队列 class Solution: def mergeKLists(self, lists: List[ListNode]) -> ListNode: import heapq queue = [] result = ListNode(-1) cur = result for index,node in enumerate(lists): if node != None: heapq.heappush(queue,(node.val,index)) while queue: val,index = heapq.heappop(queue) cur.next = lists[index] cur = cur.next lists[index] = lists[index].next if lists[index] != None: heapq.heappush(queue,(lists[index].val,index)) return result.next #分治 class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: mergeResult = ListNode(-1) cur = mergeResult while l1 and l2: if(l1.val > l2.val): cur.next = l2 l2 = l2.next else: cur.next = l1 l1 = l1.next cur = cur.next if(l1 == None): cur.next = l2 elif(l2 == None): cur.next = l1 return mergeResult.next def mergeKLists(self, lists: List[ListNode]) -> ListNode: length = len(lists) if length == 0: return None if length == 1: return lists[0] else: mid = length // 2 return self.mergeTwoLists(self.mergeKLists(lists[:mid]),self.mergeKLists(lists[mid:length]))

反思：

元组在heapq里比较的机制是从元组首位0开始，即遇到相同，就比较元组下一位，比如(1,2), (1,3)，前者比后者小。

这题刚好node值有重复的，同时ListNode无法被比较，需要用索引。

有点难的，虽说思路不难。