合并两个有序链表
Merge Two Sorted Lists
把两条已经升序排列的链表合并成一条升序链表，节点直接复用。
在力扣中练习题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = [] 输出：[]
示例 3：
输入：l1 = [], l2 = [0] 输出：[0]
提示：
- 两个链表的节点数目范围是
[0, 50] -100 <= Node.val <= 100l1和l2均按 非递减顺序 排列
解题思路
哨兵 + 尾指针 · 迭代
每次取两个头中较小的那个，接到结果链尾
两条链已经各自有序，所以只需要反复比较当前两个头节点，把较小的那个摘下来接到结果链尾。
如果结果链一开始为空，第一个节点要单独判断；用 dummy 哨兵可以消掉这个分支：tail = &dummy，之后每次都是 tail->next = ...。
dummy 指向空，tail 先停在 dummy；两条输入链的头由 list1、list2 指向。
自拟主例里有重复值 6：一个来自 A、一个来自 B。它们值相同但身份不同，画面上用 A2、B2 区分；<= 让 A 的 6 先被取走，另一个随后跟上。
当某一条链先用完，另一条剩下的整段已经有序，直接挂到 tail 后面即可，不需要再逐个比较。
9 ≤ 10，把 9（a-3）接到结果链尾；list1 后移。
list1→ null全程只改 next，没有新建节点；时间复杂度与两条链总长度成正比。
易错点
- 返回 dummy 而不是 dummy.next：答案里会多出一个哨兵节点。
- 每次忘记移动 tail：结果链的 next 被反复覆盖。
- 剩下的一段仍用 while 逐个接：结果正确但多做无用的比较，也容易在空指针处出错。
递归 · 归并
选出较小的头，剩下的交给递归
代码更短，但递归深度等于两条链总长度，最坏需要 O(m+n) 调用栈；链表很长时不如迭代稳。
递归写法的视角更小：如果 a 为空就返回 b，b 为空就返回 a；否则选出较小的头，把它的 next 指向“其余部分的合并结果”。
代码只有几行，和归并排序的 merge 完全同构。代价是递归深度等于两条链总长度，最坏 O(m+n) 的调用栈；链表很长时可能栈溢出。
如果题目没有额外限制，递归版本很适合快速表达思路；工程代码里更常用迭代版，避免深递归。
- 1任一链为空，直接返回另一条。
- 2比较两个头，选较小的作为当前节点。
- 3递归合并剩余部分，接到当前节点后面。
- 4返回当前节点。
易错点
- 递归前没有保存 next：修改当前节点的 next 后，剩余链的入口会丢失。
- 相等时没有稳定选择：虽然结果仍有序，但相同值的相对顺序会变化。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
list1 = [1,4,6,9]，list2 = [2,3,6,8,10]dummy 指向空，tail 先停在 dummy；两条输入链的头由 list1、list2 指向。
查看 C++ 代码
延伸阅读
- 哨兵节点能统一“结果为空”和“结果非空”的处理，是链表构造题的常用起点。
- 合并两条有序链是归并排序的核心步骤，第 148、23 题都会复用它。