本文详解 listnode 形式下两数相加的经典算法，重点剖析原实现中丢失头节点、逻辑错位与边界处理缺陷，并提供简洁健壮的 dummy head 解法。
本文详解 listnode 形式下两数相加的经典算法，重点剖析原实现中丢失头节点、逻辑错位与边界处理缺陷，并提供简洁健壮的 dummy head 解法。
在 LeetCode 第 2 题 “Add Two Numbers” 中，我们需将两个逆序存储的非负整数链表相加（个位在头，高位在尾），返回同样逆序表示的和链表。例如：l1 = [2→4→3]（即数字 342）、l2 = [5→6→4]（即 465），结果应为 [7→0→8]（即 807）。
原代码存在三个关键问题：
- 丢失头节点引用：l3 在循环中不断被赋值为 l3.next，最终 return l3 实际返回的是链表末尾节点，而非头节点 → 结果仅含一个值；
- 指针移动逻辑错误：l1 或 l2 提前为 null 时，未及时跳过其值参与计算，却仍重复使用已遍历节点的 val，导致数值错乱；
- 节点创建时机混乱：在循环体内“预分配”下一节点，使控制流复杂且易漏处理进位或不等长尾部。
✅ 正确解法采用 dummy head（哨兵节点）技巧，大幅提升代码清晰度与鲁棒性：
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0); // 哨兵节点，不存有效数据
ListNode tail = dummy; // tail 始终指向当前结果链表的尾节点
int carry = 0;
while (l1 != null || l2 != null || carry > 0) {
int sum = (l1 == null ? 0 : l1.val)
+ (l2 == null ? 0 : l2.val)
+ carry;
tail.next = new ListNode(sum % 10); // 创建新节点并链接
tail = tail.next; // tail 前移至新节点
carry = sum / 10;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
return dummy.next; // 跳过无意义的哨兵头节点
}? 核心设计思想：
- dummy 固定不动，作为统一入口；tail 承担动态构建职责；
- 循环条件 l1 != null || l2 != null || carry > 0 自然覆盖所有场景：两链表同步遍历、一长一短补零、最终进位（如 99 + 1 = 100）；
- 每次迭代只做三件事：算当前位值、创建并挂载新节点、更新进位与指针 —— 逻辑内聚、无冗余分支。
⚠️ 注意事项：
- 切勿在循环中直接修改 dummy 或返回 tail，否则必然丢失链表头部；
- l1 和 l2 的 next 移动必须放在该轮计算之后且独立判断，避免空指针或重复读取；
- 即使输入链表为空（虽题设为 non-empty，但健壮实现应兼容），此解法依然安全。
该解法时间复杂度为 $O(\max(m,n))$，空间复杂度为 $O(\max(m,n))$（结果链表长度），是面试与工程中推荐的标准实现范式。
