23. 合并K个升序链表

Difficulty
Hard
Tags
多路归并
排序
优先队列
堆
URL
https://leetcode-cn.com/problems/merge-k-sorted-lists/
Star
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2：
输入：lists = []
输出：[]
示例 3：
输入：lists = [[]]
输出：[]
提示：
  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • 10^4 <= lists[i][j] <= 10^4
  • lists[i] 按 升序 排列
  • lists[i].length 的总和不超过 10^4

法 1 分治法

思路
根据归并排序的思路
题解
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if len(lists) == 0:
            return None
        if len(lists) == 1:
            return lists[0]
        
        part = len(lists) // 2
        left_list = self.mergeKLists(lists[:part])
        right_list = self.mergeKLists(lists[part:])

        return self.merge(left_list, right_list)

    def merge(self, l1, l2):
        res = ListNode(0)
        cur = res
        while l1 and l2:
            if l1.val <= l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            
            cur = cur.next
        
        if l1:
            cur.next = l1
        else:
            cur.next = l2
        return res.next

优先队列

思路
采用堆实现的优先队列。
不能·直接将节点添加进去，因为节点是无法比较大小的。所以加到队列中的为（node.val, idx, node）idx为全局变量，为了使node.val相同时依旧可以比大小
题解
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if len(lists) <= 1:
            return None if len(lists) == 0 else lists[0]
            
        queue = []
        idx = 0
        # 将多个链表头节点加进去。
        # 此处为了可以比较大小，同时将节点值加进去
        # idx 为全局变量，为了使得添加进去的元组可以比较大小
        for i in range(0, len(lists)):
            if lists[i]:
                heapq.heappush(queue, (lists[i].val, idx, lists[i]))
                idx += 1

        dummy = ListNode(0)
        cur = dummy
        while queue:
            cur.next = heapq.heappop(queue)[2]
            cur = cur.next
            # 小优化，如果此时队列中没有了，直接break
            if not queue:
                break
            if cur.next:
                heapq.heappush(queue, (cur.next.val, idx, cur.next)) # 将下一个加入堆中
                idx += 1

        return dummy.next