题目

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

示例:

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

解题思路

归并法： 链表两两合并，再两两合并

优先级队列： 先保存所有head，排序，然后找最小的head，然后将最小的head的next二分插入有序的队列中，重复直到队列为空

代码

归并法：

# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def merge_2lists(self, list1: list, list2: list) -> ListNode: ret_head = ListNode(-1) p = ret_head while list1 and list2: if list1.val < list2.val: p.next = list1 list1 = list1.next else: p.next = list2 list2 = list2.next p = p.next if list1: p.next = list1 if list2: p.next = list2 return ret_head.next def mergeKLists(self, lists: List[ListNode]) -> ListNode: if not lists: return None if len(lists) == 1: return lists[0] mid = len(lists) >> 1 return self.merge_2lists(self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:]))

优先级队列法：

# Definition for singly-linked list. class ListNode(object): def __init__(self, x): self.val = x self.next = None class Solution(object): def mergeKLists(self, lists): """ :type lists: List[ListNode] :rtype: ListNode """ if not lists: return candidates = [head for head in lists if head] candidates.sort(key = lambda x: x.val) init_head = ListNode(-1) p = init_head while candidates: cur_min = candidates.pop(0) p.next = cur_min p = cur_min to_insert = cur_min.next if not to_insert: continue low, high = 0, len(candidates) - 1 while low <= high: mid = (low + high) // 2 if candidates[mid].val < to_insert.val: low = mid + 1 elif candidates[mid].val > to_insert.val: high = mid - 1 else: candidates.insert(mid, to_insert) break if low > high: candidates.insert(low, to_insert) return init_head.next