两数相加 图解题解

这道题真正在问什么

两个非负整数各用一条链表表示，数位按「低位在前」存放（个位是头节点），要求返回它们的和，同样用低位在前的链表表示。数字可能非常长，长到任何整数类型都装不下——所以别想着把链表还原成数字再相加，必须像小学竖式那样逐位处理。

为什么低位在前反而是送分设计

竖式加法天然从个位算起，因为低位产生的进位要传给高位。链表低位在前，意味着从两条链的头节点开始同步往后走，遍历顺序恰好就是加法需要的计算顺序，一遍顺序遍历直接出结果，连反转都不用。如果题目改成高位在前（LeetCode 445），反而要先用栈或反转把顺序倒过来才能加。

想通这一点，整道题就从「链表技巧题」还原成它的本质：用链表外壳包着的高精度加法模拟。

进位 carry 为什么是整个算法的核心

逐位相加时，各位之间唯一的耦合就是进位：本位的和超过 9，要往高一位送一个 1。把这件事收敛成一个变量 carry，每一位的计算就完全统一：总和 = a + b + carry，当前位写总和 % 10，新的 carry 是总和 // 10。由于每位相加最大是 9 + 9 + 1 = 19，carry 只会是 0 或 1，永远不会连环爆位。

正确性不需要额外论证——这就是竖式加法本身的规则，算法只是把人手算的过程逐字翻译成代码。真正的功夫全在边界处理上。

循环条件为什么要带上 carry

两条链长度可能不同，短的先走完后，缺的位当 0 参与运算即可，不需要补节点。但最容易漏的一种情况是：两条链都走完了，carry 还是 1——比如 5 + 5，两条链各一个节点，加完后必须再补一个最高位节点存这个 1，否则 10 会被算成 0。

把循环条件写成「l1 或 l2 或 carry 任一非空非零就继续」，最后这次补位就被自然纳入循环，不用在循环外单独写一段收尾代码。这是本题第一坑，也是面试官检查你是否真正模拟过竖式的试金石。

哑结点、复杂度与常见变体

结果链表的头节点在循环第一轮才产生，所以照例用哑结点 dummy 起头，接第一个节点和接后续节点写法一致，最后返回 dummy.next。

时间 O(max(m,n))：两条链各扫一遍，循环轮数由较长的链加上可能的一次补位决定。空间 O(max(m,n))：结果链表最长比长链多一个节点；除结果外只用了 carry 一个额外变量。变体方面，高位在前的版本先把两条链压栈再从栈顶逐位相加、用头插法建结果，核心的 carry 逻辑与本题完全相同。

Python

def addTwoNumbers(l1, l2):
    dummy = cur = ListNode(0)   # 哑结点
    carry = 0
    while l1 or l2 or carry:
        a = l1.val if l1 else 0
        b = l2.val if l2 else 0
        carry, d = divmod(a + b + carry, 10)
        cur.next = ListNode(d); cur = cur.next
        l1 = l1.next if l1 else None
        l2 = l2.next if l2 else None
    return dummy.next

C++

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2){
    ListNode dummy(0), *cur = &dummy;
    int carry = 0;
    while(l1 || l2 || carry){
        int s = (l1?l1->val:0) + (l2?l2->val:0) + carry;
        carry = s / 10;
        cur->next = new ListNode(s % 10); cur = cur->next;
        if(l1) l1 = l1->next;
        if(l2) l2 = l2->next;
    }
    return dummy.next;
}

Java

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