LeetCode 合并K个排序链表题解

LeetCode 合并K个排序链表题解题目描述合并 k 个排序链表返回合并后的排序链表。示例输入lists [[1,4,5],[1,3,4],[2,6]]输出[1,1,2,3,4,4,5,6]解题思路方法堆思路使用最小堆存储每个链表的当前节点。初始化堆将每个链表的第一个节点加入堆中。重复以下步骤弹出堆顶节点将其加入结果链表如果堆顶节点有下一个节点将下一个节点加入堆中复杂度分析时间复杂度O(n log k)空间复杂度O(k)代码实现import heapq class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def merge_k_lists(lists): heap [] for i, node in enumerate(lists): if node: heapq.heappush(heap, (node.val, i, node)) dummy ListNode() curr dummy while heap: val, i, node heapq.heappop(heap) curr.next node curr curr.next if node.next: heapq.heappush(heap, (node.next.val, i, node.next)) return dummy.next # 测试 def test_merge_k_lists(): lists [ListNode(1, ListNode(4, ListNode(5))), ListNode(1, ListNode(3, ListNode(4))), ListNode(2, ListNode(6))] result merge_k_lists(lists) while result: print(result.val, end ) result result.next if __name__ __main__: test_merge_k_lists()总结合并K个排序链表是堆的典型应用通过维护一个大小为 k 的堆来合并 k 个排序链表。