21. 合并两个有序链表 (Easy)
专题归类： 04-链表 LeetCode 链接： https://leetcode.cn/problems/merge-two-sorted-lists/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
- 输入：l1 = [1,2,4], l2 = [1,3,4]
- 输出：[1,1,2,3,4,4]
题目详细分析
- 数据范围： 两个链表的节点数分别在 [0, 50] 和 [0, 50] 范围内，节点值在 [-100, 100] 范围内
- 输入特征： 两个链表都已按升序排列，可能为空，可能长度不同
- 核心约束： 不能创建新节点，必须通过拼接给定的节点组成新链表
- 隐藏条件： 链表已有序这一条件意味着我们可以使用类似归并排序中合并的双指针法，不需要排序
- 边界条件： 两个链表都为空、其中一个为空、两个链表长度相差很大
小白版直白理解
就像你有两叠已经按大小排好序的扑克牌，现在要把它们合并成一叠，并且还是从小到大排列。
方法很简单：同时看两叠牌最上面的那张，哪张更小就把它放到新的一叠里，然后继续比较剩下的最上面那张。直到某一叠空了，就把另一叠剩下的全部接上去。
解题思路
思路一：迭代法 + 虚拟头节点（推荐）
为什么这样想： 需要不断从两个链表中选取较小节点接到结果链表的尾部。使用「虚拟头节点」可以统一处理空链表的情况，不需要单独处理结果链表的第一次插入。
关键洞察： 每次取较小节点接到 cur 后面后，对应链表的指针前移一位。当其中一个链表遍历完，直接将另一个链表剩余部分接到结果后面即可。
def mergeTwoLists(l1, l2):
"""迭代法：虚拟头节点 + 双指针"""
dummy = ListNode(0) # 虚拟头节点
cur = dummy
while l1 and l2:
if l1.val <= l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
# 将剩余部分直接拼接
cur.next = l1 if l1 else l2
return dummy.next思路二：递归法
思路讲解： 找出两个头节点中的较小者，将其 next 指向「剩余部分合并后的结果」。递归的终止条件是某个链表为空，此时直接返回另一个链表。代码非常简洁，但需要理解递归的调用栈。
关键洞察： 递归法的核心是「谁小谁当头，剩下的递归合并」。每次递归确定一个节点在最终链表中的位置。
def mergeTwoLists(l1, l2):
"""递归法"""
if not l1:
return l2
if not l2:
return l1
if l1.val <= l2.val:
l1.next = mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = mergeTwoLists(l1, l2.next)
return l2易错点
- 虚拟头节点返回： 返回的是
dummy.next而不是dummy或cur - cur 的移动： 每次拼接后要记得
cur = cur.next，否则结果链表只有一个节点 - 剩余节点拼接： 最后要用
cur.next = l1 if l1 else l2，而不是用 while 循环一个个拼接 - 递归终止条件： 两个链表都可能为空，所以需要分别检查
not l1和not l2 - 相等值处理： 用
<=保证合并的稳定性（先取 l1 的节点）
框架提炼
合并两个有序链表模板： 虚拟头节点 + 双指针比较，是归并排序的合并步骤。
def merge_two(l1, l2):
dummy = ListNode(0)
cur = dummy
while l1 and l2:
if l1.val <= l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 if l1 else l2
return dummy.next这个模板在以下场景被直接复用：
- 23. 合并 K 个升序链表的分治解法
-
- 排序链表的归并步骤
关联题目
- 23-合并K个升序链表 — 从两个扩展到 K 个，可以用分治或最小堆
- 148-排序链表 — 链表的归并排序，合并操作直接复用本题代码
- 2-两数相加 — 同步遍历两个链表，处理进位逻辑