2. 两数相加（Add Two Numbers）

频次 ★★★★ · 难度 🟡 · 高频：全厂

题目

两个非空链表分别表示两个非负整数，每位数字逆序存储（个位在链表头）。将两数相加，以同样的逆序链表形式返回结果。

示例：

输入: l1 = [2,4,3], l2 = [5,6,4]   (代表 342 + 465)
输出: [7,0,8]                       (代表 807)

思路

因为是逆序存储（个位在前），正好符合从低位到高位逐位相加、处理进位的顺序，不需要像”字符串大数相加”那样先反转。同步遍历 l1、l2，每一位算 l1.val + l2.val + carry，取 % 10 作为当前位，/ 10 作为下一位的进位。用哑节点简化”结果链表还没有头节点”的初始状态。

代码

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode cur = dummy;
    int carry = 0;
 
    while (l1 != null || l2 != null || carry != 0) {
        int sum = carry;
        if (l1 != null) {
            sum += l1.val;
            l1 = l1.next;
        }
        if (l2 != null) {
            sum += l2.val;
            l2 = l2.next;
        }
        carry = sum / 10;
        cur.next = new ListNode(sum % 10);
        cur = cur.next;
    }
    return dummy.next;
}

复杂度

• 时间：O(max(m, n)) — m、n 分别是两条链表的长度
• 空间：O(max(m, n)) — 结果链表的长度（不算输入）

边界条件

• 两条链表长度不同（如 [9,9] 和 [1]）：短链表提前变为 null，sum 只累加长链表当前位和 carry，循环条件 l1 != null || l2 != null 保证会继续处理长链表剩余部分。
• 最高位相加产生新的进位（如 [5] + [5] = [0,1]）：循环条件里的 carry != 0 保证会多生成一个节点存放这个进位。
• 其中一条链表为空：等价于直接返回另一条链表的深拷贝（代码里会自然地把 carry 当 0 处理，逐位复制）。

变式

• 如果数字是正序存储（最高位在链表头，更符合日常书写习惯）：不能像本题这样直接从头对齐相加，需要先把两条链表反转，按本题方法相加后再把结果反转回来；或者用递归从尾部开始处理进位。
• 三个数相加：思路一样，sum 累加三条链表当前位再取模、算进位，扩展性很好。

易错点

• 循环条件里不能漏掉 carry != 0：两条链表都走完了，但最高位相加还有进位（如 5 + 5 = 10），需要再多出一个节点。
• 每一位都要单独判断 l1 != null、l2 != null 再取值和移动指针，不能假设两条链表长度相同。

面试追问

• 为什么这道题用逆序存储，而不是更符合直觉的正序存储？ 逆序存储让”个位对齐”变得天然简单——两个链表的头节点就是各自的个位，加法从低位到高位的运算顺序正好和链表遍历顺序一致，不需要先获取链表长度或反转；如果是正序存储，就必须先反转链表（或用递归/栈从尾部开始）才能对齐位数相加。
• 如果结果需要去掉前导 0（比如两个链表相加后最高位是 0 的情况），需要怎么处理？ 在本题的存储约定下不会出现前导 0（因为每一位都是独立数字拼接，不存在”整体去前导零”的语义），如果是字符串大数相加类的场景，需要在最后单独判断和裁剪。

关联题

• 同套路：66. 加一 —— 数组版进位模拟；415. 字符串相加 —— 字符串版
• 进阶：445. 两数相加 II —— 高位在前，需借栈或先反转，考”进位方向与遍历方向冲突怎么办”
• 知识点：低位起、carry 变量、收尾补最高位的进位模拟三步，是大数运算的通用骨架