LeetCode 每日一题 #21：合并两个有序链表｜Python 递归与迭代双解法

几年前我准备求职时，也曾一头扎进 LeetCode 的题海。从最初的“看题懵圈”到后来能在面试中从容写出最优解，每天坚持刷一道题成了我提升算法能力最有效的方式。那段经历不仅帮我顺利拿到心仪 offer，更让我养成了系统思考和高效编码的习惯。

如今工作稳定了，终于有时间把当年的刷题笔记重新整理、优化，并用Python 语言逐题讲解清楚。希望能帮助正在准备面试、转行或想夯实基础的你——少走弯路，高效进步。

关键词：链表、归并、双指针、递归、虚拟头节点
难度：简单
推荐指数：⭐⭐⭐⭐⭐（高频基础题，考察链表操作基本功）

题目描述

将两个升序链表list1和list2合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例

输入: list1 = [1,2,4], list2 = [1,3,4] 输出: [1,1,2,3,4,4] 输入: list1 = [], list2 = [] 输出: [] 输入: list1 = [], list2 = [0] 输出: [0]

约束条件

• 两个链表的节点数目范围是[0, 50]
• -100 <= Node.val <= 100
• list1和list2均按非递减顺序排列

解题思路

本题是归并排序中“合并”步骤的简化版，核心在于：

每次选择两个链表当前头结点中较小的一个，接入结果链表。

由于链表是动态结构，需谨慎处理指针连接。有两种主流实现方式：

1. 迭代法（推荐）：使用虚拟头节点 + 双指针，空间 O(1)
2. 递归法：代码简洁，但空间 O(n+m)（递归栈）

下面分别详解。

Python 代码实现

解法一：迭代法（双指针 + 虚拟头节点）

# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclassSolution:defmergeTwoLists(self,list1:Optional[ListNode],list2:Optional[ListNode])->Optional[ListNode]:# 创建虚拟头节点，简化边界处理dummy=ListNode(0)current=dummy# current 指向结果链表的尾部# 双指针遍历两个链表whilelist1andlist2:iflist1.val<=list2.val:current.next=list1 list1=list1.nextelse:current.next=list2 list2=list2.nextcurrent=current.next# 移动结果指针# 将剩余非空链表直接接上（无需逐个复制）current.next=list1iflist1elselist2returndummy.next

迭代法逐行精讲：

• dummy = ListNode(0)
  虚拟头节点避免对“结果链表头结点”的特殊判断（如第一次选谁作为头）。

• current = dummy
current始终指向已合并部分的最后一个结点，用于追加新结点。

• while list1 and list2:
  只要两个链表都非空，就比较当前头结点值。

• current.next = list1（或list2）
  直接“嫁接”整个结点（包括其后续链），不新建结点，节省空间。

• current = current.next
  移动current到新加入的结点，保持尾指针位置。

• current.next = list1 if list1 else list2
  当一个链表遍历完，另一个剩余部分天然有序，直接拼接即可。

优势：时间 O(m+n)，空间 O(1)，无递归开销，工业级首选。

解法二：递归法（简洁优雅）

classSolution:defmergeTwoLists(self,list1:Optional[ListNode],list2:Optional[ListNode])->Optional[ListNode]:# 基线条件：任一链表为空，返回另一个ifnotlist1:returnlist2ifnotlist2:returnlist1# 递归选择较小头结点，并合并其余部分iflist1.val<=list2.val:list1.next=self.mergeTwoLists(list1.next,list2)returnlist1else:list2.next=self.mergeTwoLists(list1,list2.next)returnlist2

递归法逐行精讲：

• 基线条件：若list1为空，直接返回list2（可能也为空）；反之亦然。
• 递归逻辑：
  • 若list1.val ≤ list2.val，则list1应作为当前头结点；
  • 其next应指向merge(list1.next, list2)的结果；
  • 返回list1作为本轮合并后的头。
• 自然终止：每次递归至少消耗一个结点，最终必触发基线条件。

优势：代码极简，逻辑清晰，体现分治思想。
劣势：递归深度为m+n，可能栈溢出（本题数据小，可接受）。

复杂度对比

小结 & 面试技巧

• 核心思想：双指针归并，类似“拉链”合上
• 关键技巧：
  • 迭代法用虚拟头节点统一处理头结点
  • 递归法用基线条件 + 自调用自然推进
• 常见错误：
  • 忘记处理空链表输入
  • 迭代中未移动current指针（导致死循环）
  • 递归中未正确返回新头结点
• 面试话术：

  “我可以用迭代或递归解决。迭代法通过虚拟头节点和双指针，一次遍历完成合并，空间最优。递归法则更简洁：每次选出较小头结点，将其 next 指向剩余部分的合并结果。”

• 扩展思考：
  • 如何合并 k 个有序链表？（LeetCode #23，可用堆或分治）
  • 若链表是降序，如何修改？（比较符号取反）

下期预告

明天我们将挑战第 22 题：括号生成，带你用回溯法构造所有合法的括号组合！

坚持每天一道 LeetCode，用 Python 写出优雅代码，夯实算法基础，拿下心仪 Offer！
关注专栏，不错过每日更新！