如何正确实现链表表示的两数相加（LeetCode 2 题）-java教程-PHP中文网

如何正确实现链表表示的两数相加（LeetCode 2 题）

本文详解 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）；
每次迭代只做三件事：算当前位值、创建并挂载新节点、更新进位与指针 —— 逻辑内聚、无冗余分支。

⚠️ 注意事项：