LeetCode 23. Merge k Sorted Lists 题解

LeetCode 23. Merge k Sorted Lists 题解题目描述给你一个链表数组每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中返回合并后的链表。示例 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 [[]] 输出[]解题思路方法一逐次合并思路逐个合并链表每次将当前合并结果与下一个链表合并使用合并两个有序链表的方法来合并两个链表复杂度分析时间复杂度O(k² × n)其中 k 是链表的数量n 是每个链表的长度。每次合并两个链表的时间复杂度是 O(n)需要合并 k-1 次。空间复杂度O(1)只需要常数级的额外空间。方法二分治法思路使用分治法将链表数组分成两半分别合并每一半然后将合并后的两个链表再合并复杂度分析时间复杂度O(k × n × log k)其中 k 是链表的数量n 是每个链表的长度。分治的时间复杂度是 O(log k)每次合并的时间复杂度是 O(k × n)。空间复杂度O(log k)递归调用的栈空间取决于递归的深度最多为 O(log k)。方法三优先队列思路使用优先队列最小堆来存储每个链表的头节点每次从优先队列中取出最小的节点添加到结果链表中然后将该节点的下一个节点加入优先队列重复上述过程直到优先队列为空复杂度分析时间复杂度O(k × n × log k)其中 k 是链表的数量n 是每个链表的长度。每次插入和删除操作的时间复杂度是 O(log k)总共有 k × n 个节点。空间复杂度O(k)优先队列的大小最多为 k。代码实现方法一逐次合并# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) - Optional[ListNode]: # 合并两个有序链表的函数 def mergeTwoLists(l1, l2): dummy ListNode(0) current dummy while l1 and l2: if l1.val l2.val: current.next l1 l1 l1.next else: current.next l2 l2 l2.next current current.next if l1: current.next l1 if l2: current.next l2 return dummy.next # 逐次合并链表 result None for l in lists: result mergeTwoLists(result, l) return result方法二分治法# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) - Optional[ListNode]: # 合并两个有序链表的函数 def mergeTwoLists(l1, l2): dummy ListNode(0) current dummy while l1 and l2: if l1.val l2.val: current.next l1 l1 l1.next else: current.next l2 l2 l2.next current current.next if l1: current.next l1 if l2: current.next l2 return dummy.next # 分治法合并链表 def merge(lists, left, right): if left right: return lists[left] if left right: return None mid (left right) // 2 l1 merge(lists, left, mid) l2 merge(lists, mid 1, right) return mergeTwoLists(l1, l2) return merge(lists, 0, len(lists) - 1)方法三优先队列# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next import heapq class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) - Optional[ListNode]: # 定义优先队列的比较规则 ListNode.__lt__ lambda self, other: self.val other.val # 初始化优先队列 heap [] for l in lists: if l: heapq.heappush(heap, l) # 合并链表 dummy ListNode(0) current dummy while heap: # 取出最小的节点 node heapq.heappop(heap) current.next node current current.next # 将该节点的下一个节点加入优先队列 if node.next: heapq.heappush(heap, node.next) return dummy.next测试用例测试用例 1输入lists [[1,4,5],[1,3,4],[2,6]]输出[1,1,2,3,4,4,5,6]测试用例 2输入lists []输出[]测试用例 3输入lists [[]]输出[]总结本题是链表的经典问题主要考察对链表操作和多种算法思想的理解和应用。通过使用逐次合并、分治法或优先队列我们可以高效地合并 k 个有序链表。逐次合并的核心思想是逐个合并链表每次将当前合并结果与下一个链表合并。分治法的核心思想是将链表数组分成两半分别合并每一半然后将合并后的两个链表再合并。优先队列的核心思想是使用最小堆来存储每个链表的头节点每次取出最小的节点添加到结果链表中。在实际应用中优先队列方法通常更受欢迎因为它的时间复杂度较低而且实现相对简单。这种方法不仅适用于合并 k 个有序链表问题还可以应用于许多其他需要处理多个有序序列的场景。掌握这些方法对于解决这类问题非常重要。