合并两个有序链表
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1
示例 2
示例 3
模拟答题者思考
1. 我先写暴力：把两条链表所有节点值收集到数组，排序后再逐个新建节点串起来——能过，但白白丢弃了「已有序」这一条件，还多用了 O(m+n) 额外空间。
2. 重复在哪里？每次只需要在两条链表的「当前头节点」里取较小者接到结果尾部，然后该链表的指针前移——这和合并两个有序数组的双指针一模一样，只是用指针代替下标。
3. 用哨兵 dummy + 尾指针 curr：比较 l1.val 与 l2.val，较小者挂到 curr.next，对应指针后移，curr 跟进。
4. 当其中一条链表耗尽，另一条剩余部分已经有序，直接 curr.next = l1 or l2 一次性接上，无需再逐个比较。
5. 复杂度：每个节点恰好被访问一次，时间 O(m+n)；只用到常数个指针，空间 O(1)（不计返回链表本身）。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
dummy | ListNode* | 定义：哨兵头节点，不存放有效值 维护：始终位于合并结果链表的最前端，统一处理「结果为空」等边界 更新：创建后不再移动，最终返回 dummy.next |
curr | ListNode* | 定义：合并结果链表的尾指针 维护：指向已拼接部分的最后一个节点，新节点总是接在 curr.next更新：每选中一个较小节点后 curr = curr.next，尾指针前移 |
l1 / l2 | ListNode* | 定义：两条输入链表当前待比较的节点 维护：各自沿 next 前进，始终指向「尚未接入结果」的最小候选 更新：谁被接入结果谁就 l1 = l1.next 或 l2 = l2.next |
落码步骤
1. 创建哨兵 dummy = ListNode(0)，curr = dummy
2. 当 l1 和 l2 均非空：比较值，较小者挂到 curr.next，对应指针后移，curr = curr.next
3. 一条链表耗尽后，将另一条剩余部分直接接到 curr.next
4. 返回 dummy.next（合并后的真实头节点）
代码实现
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0) # 哨兵，简化头节点处理
curr = dummy # 结果链表的尾指针
l1, l2 = list1, list2
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 or l2 # 接上剩余有序段
return dummy.nextclass Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode dummy(0); // 哨兵，简化头节点处理
ListNode* curr = &dummy; // 结果链表的尾指针
while (list1 && list2) {
if (list1->val <= list2->val) {
curr->next = list1;
list1 = list1->next;
} else {
curr->next = list2;
list2 = list2->next;
}
curr = curr->next;
}
curr->next = list1 ? list1 : list2; // 接上剩余有序段
return dummy.next;
}
};
// 时间 O(m+n)，空间 O(1)复杂度分析
O(m + n)
O(1)
常见坑
忘记移动 curr：只改了 curr.next 却不 curr = curr.next，会导致所有节点叠在同一位置、链表成环或断裂。
一条链表耗尽后仍继续 while 比较：剩余段已经有序，应直接 curr.next = l1 ? l1 : l2，否则多余循环且可能访问空指针。
返回 dummy 而非 dummy.next：哨兵节点不应出现在最终结果中。
必测边界 Case
l1 = [], l2 = [] → []
l1 = [], l2 = [0] → [0]
l1 = [1,2,4], l2 = [1,3,4] → [1,1,2,3,4,4]（相等时取 l1 即可）