从零开始学算法——链表篇3：合并两个有序链表 + 两数相加
在链表类算法题中，我们经常听到“虚拟头节点”或“哑节点”（Dummy Node）这个概念。很多初学者往往是照猫画虎，看别人用了也就跟着用。
其实可以 简单总结为“只有需要对头节点的前一个节点进行操作的时候，才需要用 dummy。”
这句话非常精准地概括了 Dummy Node 在链表修改（如删除倒数第 N 个节点、反转链表）中的作用。但在链表构建（如合并链表、两数相加）类题目中，Dummy Node 扮演了另一个至关重要的角色：消除“冷启动”差异，统一边界逻辑。
今天我们就通过“合并两个有序链表”和“两数相加”这两道经典题目，来深度解析 Dummy Node 如何让代码化繁为简。
一、 合并两个有序链表：拉链法的极致简化
题目：将两个升序链表合并为一个新的升序链表并返回。
1. 痛点分析：如果没有 Dummy Node
如果我们在不使用 Dummy Node 的情况下构建一个新链表，代码逻辑通常是这样的：
比较
list1和list2的头节点，确定谁小。将结果链表的
head指向那个较小的节点。之后的循环中，我们操作的是
cur->next。
你会发现，**“确定第一个节点”和“确定后续节点”**的逻辑是不一样的。我们需要额外的if-else来处理头节点的初始化。这就是所谓的“冷启动”问题。
2. 优化思路：虚拟头节点的“锚点”作用
使用ListNode dummy(0);在栈上创建一个虚拟节点，它的作用就像一个锚点。
cur指针最初指向dummy。此后，无论是添加第一个有效节点，还是添加第一百个节点，我们统一的操作都是
cur->next = node。
这种写法将头节点的处理逻辑降维成了普通节点的处理逻辑。
3. 代码深度解析
C++代码实现：
class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { // 在栈上创建 dummy，自动管理内存，无需手动 delete ListNode dummy(0); ListNode* cur = &dummy; ListNode* cur1 = list1; ListNode* cur2 = list2; // 核心逻辑：谁小移谁，像拉拉链一样咬合 while (cur1 && cur2) { if (cur1->val < cur2->val) { cur->next = cur1; cur1 = cur1->next; } else { cur->next = cur2; cur2 = cur2->next; } // 别忘了移动结果链表的指针 cur = cur->next; } // 优化点：链表天然的优势 // 当一个链表遍历完，另一个链表剩余部分直接接在后面即可，无需遍历 cur->next = cur1 ? cur1 : cur2; return dummy.next; } };4. 时空复杂度分析
时间复杂度：O(M + N)。其中 M 和 N 是两个链表的长度。我们最多只遍历了两个链表一次。
空间复杂度：O(1)。这是一次原地合并。我们并没有创建新的节点（除了 dummy），只是调整了原有节点的
next指针，将它们重新串联起来。
二、 两数相加：模拟加法与进位的艺术
题目：两个非空链表代表两个非负整数，数字逆序存储，请将它们相加并以链表形式返回。
1. 难点分析
这就好比我们在纸上算加法：
对齐：链表逆序存储（个位在头），刚好符合我们从低位算起的习惯。
长度不等：一个数是 3 位，一个数是 5 位，短的那个数高位要视为 0。
进位（Carry）：9 + 1 = 10，需要向后进 1。最容易忽略的是最后一位相加如果还有进位，需要补一个新的节点。
2. 代码深度解析
这段代码的精髓在于while循环的条件控制。
C++代码实现：
class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* cur = &dummy; int carry = 0; // 进位记录 // 这里的条件非常优雅：只要 l1 没走完，或者 l2 没走完，或者还有进位没处理 // 循环就继续。这完美解决了“长度不等”和“最后进位”的问题。 while (l1 || l2 || carry) { int sum = carry; // 当前位的和，先加上进位 if (l1) { sum += l1->val; l1 = l1->next; } if (l2) { sum += l2->val; l2 = l2->next; } // 创建新节点存储当前位的值（个位） cur->next = new ListNode(sum % 10); cur = cur->next; // 更新进位（十位） carry = sum / 10; } return dummy.next; } };3. 时空复杂度分析
时间复杂度：O(max(M, N))。我们需要遍历较长的那个链表，如果最后有进位，则多走一步。
空间复杂度：O(max(M, N))。注意，这里和上一题不同。上一题是重组旧节点，这一题是创建新节点。我们需要创建一个新的链表来存储结果，其长度最长为
max(M, N) + 1。
说明：
两者时间复杂度为什么一个是O(M + N)，一个是O(max(M, N))
核心区别：是一个一个走还是一对一对走
比如第一题我们一次循环迭代指针只做了一次移动，而第二题是一起移动的，这就是区别。
三、 总结：Dummy Node 的双重境界
我们可以把 Dummy Node 的作用总结为两层境界：
防御层（操作前驱）： 当你需要删除或插入位置
i的节点时，你需要找到位置i-1。如果i=0（头节点），i-1不存在。此时 Dummy Node 充当了那个永远存在的pre节点，统一了操作逻辑。构建层（统一构建）： 也就是本文讨论的场景。当你需要从无到有构建一条新链表时，结果链表的头节点在循环开始前往往是未知的（或者需要复杂的判断逻辑来生成）。此时 Dummy Node 作为一个静态的占位符，让我们可以无脑执行
cur->next = new_node，统一了初始化逻辑。
这就是链表中“虚拟头节点”的本质。