一、引言

在练习算法题的过程中，我们经常会遇到 LeetCode 上看似简单却暗藏陷阱的题目。今天分享的是经典的“#2 两数相加”（Add Two Numbers），我将结合自己的思路和调试过程，带你一起深入理解链表加法的要点与常见误区。

二、题目描述

给定两个非空链表，它们分别表示两个非负整数，数字按照逆序存储，每个节点只存储一位数字。 请将两数相加，并以相同形式返回一个表示和的链表。 你可以假设，除了数字 0 本身，这两个数都不会以 0 开头。

示例：

• 输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807

• 输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出：[8,9,9,9,0,0,0,1]

提示：

• 链表长度 ∈ [1, 100]

• 节点值 ∈ [0, 9]

• 题目数据保证不含前导零

三、初始思路与陷阱

1. 整体数字转整型再相加

   • 初衷：将链表的各位“提取”后，按十进制重组为一个整数，直接相加再拆分。

   • 遇到的问题：测试用例长度可能高达 100 位，int/long 都会越界；即便使用 BigInteger，频繁的字符串与数字转换也容易出错，效率低下。

2. 误用链表反转

   • 误区：以为题目说“逆序存储”就需要将链表反转，实际反转后再逐位相加，反而多此一举。

   • 真相：由于最低位已在链表头部，直接从头遍历即可按位相加，反转操作完全可以省略。

四、正确解法思路

1. 逐位相加 + 进位

   • 设指针 p、q 分别指向 l1、l2 的当前节点，初始都指向头节点。

   • 使用变量 carry 记录进位，初始为 0。

   • 循环条件：p != null || q != null 或 carry != 0。

2. 每一步操作

   • 取值 x = (p != null) ? p.val : 0，y = (q != null) ? q.val : 0。

   • 计算 sum = x + y + carry；新节点值为 sum % 10，更新 carry = sum / 10。

   • 将新节点追加到结果链表尾部。

   • 分别向后移动 p、q。

3. 结束条件

   • 当两链表都遍历完 且 carry == 0 时，循环结束。

   • 返回结果链表的下一个节点（跳过哨兵头节点）。

五、完整代码（Java 实现）

public class AddTwoNumbers {
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode curr = dummyHead;
        int carry = 0;
        
        ListNode p = l1, q = l2;
        while (p != null || q != null || carry != 0) {
            int x = (p != null) ? p.val : 0;
            int y = (q != null) ? q.val : 0;
            int sum = x + y + carry;
            
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            
            if (p != null) p = p.next;
            if (q != null) q = q.next;
        }
        
        return dummyHead.next;
    }
​
    // 链表节点定义
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
    }
}

解析：

• 使用哨兵节点 dummyHead 简化头节点处理。

• 循环条件中额外判断 carry != 0，确保最后的进位也能被处理。

• 每次循环中，将相加结果拆分成当前位和新的进位。

六、总结与心得

• 不要提前“数字化”：当数据规模超过基本类型范围时，字符串或大整数操作开销大且易错，链表逐位运算更直接。

• 明确题意：题目给出的“逆序存储”即意味着最低位在链表头，无需额外反转。

• 边界与细节：注意空链表（或长度不等）的处理，以及最后的进位节点。

通过这道题，可以巩固链表遍历、进位思路，以及如何使用哨兵节点简化链表操作。