题目描述
把两条升序链表合并成一条升序链表。
链表 A = 1 → 2 → 4
链表 B = 1 → 3 → 4
输出 = 1 → 1 → 2 → 3 → 4 → 4
思路解析
挂一个 dummy 哨兵当结果起点。比较 p1、p2 当前值：小的那个接到结果尾巴，它自己前进一步。某条走完，把另一条剩下的整段直接接上。
起点 · p1、p2 各指头：p1 指 A 的头 1，p2 指 B 的头 1。结果（dummy 之后）目前为空。开始比较。
1(A) ≤ 1(B) · 取 A 的 1：1 ≤ 1，取 A 的 1（高亮）接入结果，p1 前进到 2。结果：1。
2(A) > 1(B) · 取 B 的 1：2 > 1，取 B 的 1，p2 前进到 3。结果：1 → 1。
2(A) < 3(B) · 取 A 的 2：2 < 3，取 A 的 2，p1 前进到 4。结果：1 → 1 → 2。
4(A) > 3(B) · 取 B 的 3：4 > 3，取 B 的 3，p2 前进到 4。结果：1 → 1 → 2 → 3。
4(A) ≤ 4(B) · 取 A 的 4：4 ≤ 4，取 A 的 4，p1 走到头（A 用完）。结果：1 → 1 → 2 → 3 → 4。
A 用完 · B 剩下的整段接上：A 已空，B 还剩 4，直接把它整段接到结果尾巴（不用再逐个比）。最终：1 → 1 → 2 → 3 → 4 → 4。
「合并有序序列」的通用骨架：哨兵起头、双指针比较取小、接完前进、末尾接残段。归并排序的 merge、合并 K 个链表都从它来。
参考代码（Python）
Python
1dummy = tail = ListNode() # 哨兵 + 结果尾指针
2while l1 and l2:
3 if l1.val <= l2.val: # 谁小接谁
4 tail.next = l1; l1 = l1.next
5 else:
6 tail.next = l2; l2 = l2.next
7 tail = tail.next # 尾指针前移
8tail.next = l1 or l2 # 剩下的整段接上
9return dummy.next复杂度分析
- 时间复杂度：O(m+n) —— 每个节点接一次
- 空间复杂度：O(1) —— 只接指针，不新建节点
套路模板
记住骨架：哨兵起头、谁小接谁、尾指针前移、最后接残段。这是归并思想在链表上的标准实现。
Python
1dummy = tail = ListNode()
2while a and b:
3 if a.val <= b.val: tail.next, a = a, a.next
4 else: tail.next, b = b, b.next
5 tail = tail.next
6tail.next = a or b # 接残段
7return dummy.next易错点
- ❌ 不用哨兵，纠结结果头 → ✅ 用 dummy 哨兵统一处理（省去"第一个节点特殊"的麻烦）
- ❌ 忘了接剩余链 → ✅ tail.next = a or b（一条先空后，另一条剩余必须接上）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。