题目描述
把两条升序链表合并成一条升序链表。
思路解析
可以把两条链所有值倒进一个数组、排好序、再 new 一条新链表——但这要 O(m+n) 额外空间，还浪费了「两条已经有序」这个条件，凭空多做一次排序。
转折：两条都有序，所以最小值一定在某条表头，不用全排。挂一个 dummy 哨兵当结果起点、tail 跟在结果尾巴。比较 l1、l2 当前值，小的接到 tail 后面、它自己前进一步。某条走完，把另一条剩下的整段直接接上。下面一帧一个动作慢放。
起点 · l1、l2 各指头 · 结果为空：l1 指 A 的头 1，l2 指 B 的头 1。结果链表（dummy 之后）目前全是虚线占位，空着。开始逐个比较表头。
第 1 轮 · 比两个表头：每一轮只盯两个表头：l1 是 1、l2 是 1。因为两条都升序，更小的那个一定是当前所有剩余里最小的，接它绝不会破坏有序。下面决定取谁。
比较 · 1(A) ≤ 1(B) · 取 A 的 1：两头都是 1，取小用 小于等于：l1 的 1 接到结果（虚线变实、长出第一个节点 1），tail 指向它，l1 前进到 2。结果：1。
比较 · 2(A) 大于 1(B) · 取 B 的 1：现在 l1 是 2、l2 是 1：2 大于 1，取 B 的 1 接到结果，tail 前移，l2 前进到 3。结果：1 → 1。
比较 · 2(A) 小于 3(B) · 取 A 的 2：l1 是 2、l2 是 3：2 小于 3，取 A 的 2，tail 前移，l1 前进到 4。结果：1 → 1 → 2。
比较 · 4(A) 大于 3(B) · 取 B 的 3：l1 是 4、l2 是 3：4 大于 3，取 B 的 3，tail 前移，l2 前进到 4。结果：1 → 1 → 2 → 3。
比较 · 4(A) ≤ 4(B) · 取 A 的 4：两头都是 4，小于等于取 A 的 4，l1 走到头——A 用完了（l1 变空，循环 while l1 and l2 即将退出）。结果：1 → 1 → 2 → 3 → 4。
负例 · A 空 · B 剩段整段接上：负例分支：A 已空，不再逐个比，直接 tail.next = l1 or l2 把 B 剩下的 4 整段接到结果尾巴。最终：1 → 1 → 2 → 3 → 4 → 4。
「合并有序序列」的通用骨架：哨兵起头、双指针比较取小、接完前进、末尾接残段。归并排序的 merge、合并 K 个链表都从它来。
参考代码（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) —— 只挪指针、不新建节点，复用原有节点
套路模板
记住骨架：哨兵起头、谁小接谁、尾指针前移、最后接残段。这是归并思想在链表上的标准实现。
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易错点
- 错误写法：循环后忘了 tail.next = l1 or l2 → 正确写法：循环退出后必须接残段（while l1 and l2 一条空就退出，另一条剩的整段没接上会丢节点）
- 错误写法：不用哨兵，纠结结果头 → 正确写法：用 dummy 哨兵统一处理（省去「第一个节点谁当头」的特判，tail 从 dummy 起步即可）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。