[23][困难][堆] 合并K个排序链表

题目描述

23. 合并K个排序链表

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

示例:

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

解题思路

归并排序的基本思路, 配合堆结构实现.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        n = len(lists)
        pq = [(lists[i].val, count, lists[i]) for count, i in enumerate(range(n)) if lists[i]]  # 排除空数组
        heapq.heapify(pq)
        index = n  # 使用index表示结点被发现的顺序, 因为相同值结点的先后顺序不重要, 因此加入一个递增的数值, 避免比较涉及到结点(无法比较)

        root, node = None, None
        while pq:
            _, _, t_node = heapq.heappop(pq)
            if root is None:
                root = t_node
                node = t_node
            else:
                node.next = t_node
                node = t_node

            if t_node.next is not None:
                next_node = t_node.next
                heapq.heappush(pq, (next_node.val, index, next_node))
                index += 1

        return root

相关题目

• [378][中等][堆][二分] 有序矩阵中第K小的元素