【LeetCode刷题】合并 K 个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 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 <=
• 0 <= lists[i].length <= 500
• <= lists[i][j] <=
• lists[i]按升序排列
• lists[i].length的总和不超过

解题的算法设计

分治法（Divide and Conquer）的核心是「分而治之」：

• 分：将 “合并 K 个链表” 这个复杂问题，拆解为多个 “合并 2 个升序链表” 的简单子问题（因为合并 2 个升序链表是基础且高效的操作）；
• 治：递归解决每个子问题（合并子区间内的链表）；
• 合：将子问题的结果再次合并，最终得到完整的合并结果。

该思路的本质是把 “一次面对 K 个链表选最小值” 的高开销操作，转化为 “多次面对 2 个链表选最小值” 的低开销操作，最终将时间复杂度从暴力法的O(Nk)优化到O(N log k)（N 为总节点数，k 为链表数量）。

算法步骤

步骤 1：预处理（边界条件处理）

首先判断输入的链表列表是否为空（if not lists）：

• 若为空，直接返回None（无链表可合并）；
• 若不为空，进入分治递归流程。

步骤 2：递归分治（拆分问题）

调用核心递归函数_merge(lists, left, right)，参数left和right表示当前要处理的链表区间（初始为0到len(lists)-1），递归逻辑如下：

1. 递归终止条件：当left == right时，说明当前区间只剩 1 个链表，无需合并，直接返回该链表（最小子问题的解）；
2. 拆分区间：计算区间中点mid = (left + right) // 2，将当前区间拆分为左半区（left ~ mid）和右半区（mid+1 ~ right）；
3. 递归处理子区间：
   • 递归处理左半区，得到左半区的合并结果left_list；
   • 递归处理右半区，得到右半区的合并结果right_list；
4. 合并子结果：调用_merge_two_lists将left_list和right_list（两个升序链表）合并为一个升序链表，作为当前区间的合并结果返回。

步骤 3：合并两个升序链表（核心子问题）

_merge_two_lists(l1, l2)负责解决最基础的 “合并 2 个升序链表” 问题，执行逻辑：

1. 虚拟头节点：创建一个虚拟头节点dummy = ListNode(0)，用于简化链表拼接（避免处理 “头节点为空” 的边界情况）；
2. 双指针遍历：用curr指针指向dummy，同时遍历l1和l2：
   • 比较l1.val和l2.val，将值更小的节点接在curr.next；
   • 移动对应链表的指针（比如l1.val < l2.val则l1 = l1.next）；
   • 移动curr指针（curr = curr.next），准备接下一个节点；
3. 拼接剩余节点：当l1或l2有一个遍历完时，将未遍历完的链表直接接在curr.next（因为链表本身是升序的，剩余节点无需再比较）；
4. 返回结果：返回dummy.next（跳过虚拟头节点，得到合并后的真实头节点）。

示例演示（以lists = [[1,4,5],[1,3,4],[2,6]]为例）

1. 初始调用_merge(lists, 0, 2)，mid = 1，拆分左区间(0,1)、右区间(2,2)；
2. 处理右区间(2,2)：终止条件触发，返回[2,6]；
3. 处理左区间(0,1)：mid=0，拆分左(0,0)（返回[1,4,5]）、右(1,1)（返回[1,3,4]），合并这两个链表得到[1,1,3,4,4,5]；
4. 合并左区间结果[1,1,3,4,4,5]和右区间结果[2,6]，最终得到[1,1,2,3,4,4,5,6]。

说明

• 虚拟头节点：是合并两个链表的经典技巧，避免反复判断 “结果链表是否为空”，简化代码；
• 剩余节点拼接：无需循环遍历剩余节点，直接拼接即可，减少冗余操作；
• 区间拆分：用整数除法//计算mid，避免浮点误差，保证区间拆分对称。

复杂度分析

• 时间复杂度：O(N log k)
  • 每一层递归的合并操作总耗时为O(N)（遍历所有节点）；
  • 递归的层数为log k（每次拆分区间减半，直到只剩 1 个链表）；
• 空间复杂度：O(log k)
  • 递归调用栈的深度为log k（拆分 k 个链表需要log k层递归）。

Python代码

# 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): # 边界处理1：空输入 if not lists: return None # 边界处理2：过滤列表中的空链表（关键！避免递归时传入None） lists = [l for l in lists if l is not None] # 过滤后无有效链表 if not lists: return None # 启动分治合并 return self._merge(lists, 0, len(lists) - 1) def _merge(self, lists, left, right): # 分治终止条件：左右指针重合（只剩1个链表） if left == right: return lists[left] # 计算中点，拆分区间 mid = (left + right) // 2 # 递归合并左半区和右半区 left_list = self._merge(lists, left, mid) right_list = self._merge(lists, mid + 1, right) # 合并两个升序链表 return self._merge_two_lists(left_list, right_list) def _merge_two_lists(self, l1, l2): # 合并两个升序链表的核心逻辑 dummy = ListNode(0) # 虚拟头节点，简化拼接 curr = dummy # 双指针遍历两个链表，选择更小的节点拼接 while l1 and l2: if l1.val < l2.val: curr.next = l1 l1 = l1.next else: curr.next = l2 l2 = l2.next curr = curr.next # 拼接剩余未遍历完的链表（本身已是升序） curr.next = l1 if l1 else l2 # 返回合并后的真实头节点（跳过虚拟头） return dummy.next # ===================== 工具函数：用于测试 ===================== def build_linked_list(nums): """根据列表构建链表（如 [1,4,5] → 1→4→5）""" dummy = ListNode(0) curr = dummy for num in nums: curr.next = ListNode(num) curr = curr.next return dummy.next def print_linked_list(head): """打印链表（如 1→4→5 → [1,4,5]）""" res = [] while head: res.append(head.val) head = head.next return res # ===================== 测试用例 ===================== if __name__ == "__main__": solution = Solution() # 测试用例1：常规场景（题目示例） lists1 = [ build_linked_list([1, 4, 5]), build_linked_list([1, 3, 4]), build_linked_list([2, 6]) ] merged1 = solution.mergeKLists(lists1) print("测试用例1结果：", print_linked_list(merged1)) # 预期：[1,1,2,3,4,4,5,6] # 测试用例2：包含空链表 lists2 = [ None, build_linked_list([5]), None, build_linked_list([1, 2, 3]), build_linked_list([4]) ] merged2 = solution.mergeKLists(lists2) print("测试用例2结果：", print_linked_list(merged2)) # 预期：[1,2,3,4,5] # 测试用例3：所有链表为空 lists3 = [None, None, None] merged3 = solution.mergeKLists(lists3) print("测试用例3结果：", print_linked_list(merged3)) # 预期：[] # 测试用例4：只有1个链表 lists4 = [build_linked_list([10, 20, 30])] merged4 = solution.mergeKLists(lists4) print("测试用例4结果：", print_linked_list(merged4)) # 预期：[10,20,30]

LeetCode提交代码

# 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[Optional[ListNode]]) -> Optional[ListNode]: # 边界处理：空输入或所有链表为空 if not lists: return None return self._merge(lists, 0, len(lists) - 1) def _merge(self, lists, left, right): # 分治终止条件：左右指针重合 if left == right: return lists[left] mid = (left + right) // 2 # 递归合并左右两个子数组的链表 left_list = self._merge(lists, left, mid) right_list = self._merge(lists, mid + 1, right) # 合并两个升序链表 return self._merge_two_lists(left_list, right_list) def _merge_two_lists(self, l1, l2): # 合并两个升序链表的辅助函数 dummy = ListNode(0) curr = dummy while l1 and l2: if l1.val < l2.val: curr.next = l1 l1 = l1.next else: curr.next = l2 l2 = l2.next curr = curr.next # 拼接剩余节点 curr.next = l1 if l1 else l2 return dummy.next

程序运行截图展示

总结

本文介绍了一种高效合并多个升序链表的分治算法。算法通过递归将链表数组不断拆分为更小的子问题（两两合并），最终将所有链表合并为一个有序链表。关键步骤包括：边界条件处理、递归分治拆分链表区间、合并两个有序链表的子问题。该算法时间复杂度为O(Nlogk)，空间复杂度为O(logk)，其中k为链表数量，N为总节点数。Python实现中使用了虚拟头节点简化合并操作，并通过过滤空链表优化性能。测试用例验证了算法在常规、空链表及单链表等情况下的正确性。