LeetCode 21简单链表 · 双指针
合并两个有序链表 图解题解
两条有序链表各出一个头节点比大小，小的接到结果链末尾——双指针穿针引线，一遍合并完成。
合并两列已按号排好的队伍，不用全部打散重排：两队各出一个人站在前面比号码，号小的跟在结果队尾（tail.next 指向它），然后 tail 前进、那队再出下一个。每次只看两个头，比完接走、指针前移，走完两队长度之和就拼好了，O(1) 额外空间，dummy 头节点免去处理空结果的特判。
这道题到底在问什么
合并两个升序链表，返回一个新的升序链表。
- list1
- 1→2→4
- list2
- 1→3→4
- 输出
- 1→1→2→3→4→4
最优解：一步一步想明白
- 3链表本来已经分别有序，没必要全部打散排序。
- 4比较 list1 和 list2 的当前节点，把更小的接到 tail 后面，然后 tail 前进。
- 5tail=dummy三行同时看：上面两个是待比较链表，下面是结果链表。tail 从 dummy 出发，专门负责接新节点。
- 6相等时先接 list1关键的比较决策帧：每一步只看两个链表的头。这里 1 和 1 相等，为保持稳定，约定相等时选 list1。
- 7tail.next = l1把胜出的节点接到 tail 后面，然后 tail 前进。tail 不前进，下一次就会覆盖刚接上的节点。
- 8list2 更小现在比较 2 和 1，list2 的 1 更小，于是接 list2 的 1。每一步都能看清「谁更小、谁被接走」，而不是直接跳到最终结果。
- 9tail 前进到新尾接完 list2 的 1，tail 再次来到结果链表尾部。接下来只重复“比较→接上→前进”。
- 10tail.next = rest当一个链表空了，另一边剩下的部分本来就是有序的，可以整段接上，不需要逐个新建节点。
- 11比较两个头 → tail.next 接较小 → tail 与该链各前进一步慢放接节点这一刻。比较两个头：2 比 3 小，就把 list1 的 2 接到 tail 后面，tail 前进到 2，同时 list1 的指针也前进。每一步只接更小的那个头，这就是合并的全部秘密。而 dummy 的作用，是让接第一个节点和接后面的节点用同一行代码。
- 14链表题里 dummy 能消灭很多头结点特判。
- 17tail stuck如果接上节点后 tail 不前进，下一次 tail.next 会覆盖刚接的节点。
- 22这题学完不要乱跳，下一步去 对应专题 连刷同类题；卡住时用 AI 答疑追问“为什么这一步成立”，比只背答案更稳。
⚠️ 容易写错的地方
✗ 错：不用 dummy，头结点分支很多
✓ 对：虚拟头结点统一处理
第一次接节点和后续接节点逻辑一致。
✗ 错：接完忘记 tail 前进
✓ 对：tail = tail.next
否则后续节点会覆盖同一个位置。
✗ 错：循环后逐个接剩余节点
✓ 对：tail.next = list1 or list2
剩余部分本身已经有序。
完整代码（Python / C++ / Java）
Python
class Solution:
def mergeTwoLists(self, list1, list2):
dummy = ListNode(0)
tail = dummy
while list1 and list2:
if list1.val <= list2.val:
tail.next = list1
list1 = list1.next
else:
tail.next = list2
list2 = list2.next
tail = tail.next
tail.next = list1 or list2
return dummy.nextC++
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode dummy(0);
ListNode* tail = &dummy;
while (list1 && list2) {
if (list1->val <= list2->val) {
tail->next = list1;
list1 = list1->next;
} else {
tail->next = list2;
list2 = list2->next;
}
tail = tail->next;
}
tail->next = list1 ? list1 : list2;
return dummy.next;
}
};Java
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
tail.next = list1;
list1 = list1.next;
} else {
tail.next = list2;
list2 = list2.next;
}
tail = tail.next;
}
tail.next = list1 != null ? list1 : list2;
return dummy.next;
}
}套路模板 · 挖空骨架
# 链表题先固定三件事：dummy、当前指针、下一跳
dummy = ListNode(0)
tail = dummy
while 还有节点要处理:
nxt = 当前节点.next # 改指针前先存后继
tail.next = 选中的节点 # 只改一根箭头
tail = tail.next # tail 必须跟着走
当前指针 = nxt
return dummy.nextListNode dummy(0);
ListNode* tail = &dummy;
while (还有节点要处理) {
ListNode* nxt = cur->next; // 改指针前先存
tail->next = cur; // 接上选中的节点
tail = tail->next; // tail 前进
cur = nxt;
}
return dummy.next;ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (还有节点要处理) {
ListNode nxt = cur.next; // 改指针前先存
tail.next = cur; // 接上选中的节点
tail = tail.next; // tail 前进
cur = nxt;
}
return dummy.next;复杂度
时间复杂度
O(m+n)
每个节点只接一次
空间复杂度
O(1)
迭代写法只用几个指针
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 合并两个有序链表 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
递归能做吗？+
可以：较小头节点的 next 指向「递归合并剩余两条链」的结果；但调用栈是 O(m+n) 空间。
会新建节点吗？+
通常不会。主流写法直接复用原节点，只改 next 指针，所以空间是 O(1)。
为什么要用 dummy 哨兵？+
它让「接第一个节点」和「接后续节点」走完全相同的逻辑，省掉对头节点的特判。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。