LC2　两数相加¶

中等通过率 47.1%python3核心代码模式链表样例通过牛客 AC递归链表数学

牛客原题　源码

讲解章节：链表

一句话

两个逆序存放的十进制数用链表给出，逐位相加后仍按逆序返回一条新链。

解题思路¶

这题考什么¶

题面把数字低位放在链表头，这不是刁难，而是把竖式加法的天然顺序摆好了：手算加法就是从个位往高位进位，而链表只能从头往后走，两者方向正好一致。于是整题退化成一次同步遍历，边走边算「本位和 = a + b + 进位」。

真正要想清楚的是循环什么时候停。停在「两条链都走完」是错的，因为最高位还可能留着一个进位（99 + 1 = 100 会多出一位）。条件写成「l1 还有、或 l2 还有、或 carry 非零」，三者全空才收工。

长度不等也不必先补齐：短链走完之后取值按 0 处理，等价于把 617 看成 0617，竖式加法本来就是这么对齐的。链表的指针搬移见链表。

数据规模与复杂度¶

每条链最多 100 个节点，每位是 0..9。一趟遍历 O(max(m, n)) 时间，结果链最长 max(m, n) + 1 个节点，除去结果本身只用 carry 一个变量。另一条思路是把两条链还原成 Python 整数相加再拆位——Python 的整数没有溢出， 100 位数也算得动，但那是绕开题意：题目考的是链表上的进位处理，而且换成 C++ 或 Java 时 100 位十进制数早就超出 64 位整数了。

坑在哪¶

循环条件必须带上 carry。只写 while l1 or l2，输入 [9,9] 与 [1] 会输出 [0,0] 而不是 [0,0,1]，最高位的进位被整条丢掉；
进位是 total // 10 不是布尔值。虽然单位相加最大 9 + 9 + 1 = 19、进位只会是 0 或 1，但写成整除才是「这一位溢出了多少」的原义，换成其他进制时不用改逻辑；
前进指针要带空判断：l1 = l1.next 在 l1 已经是 None 时直接 AttributeError，必须写成 l1.next if l1 else None；
用哨兵节点 dummy 起手，返回 dummy.next。不用哨兵就得为「第一个结果位」单开一条建头分支，循环体里还要每轮判一次「现在是不是第一位」。

样例复核¶

[9,9,9,9,9,9,9] + [9,9,9,9] 即 9999999 + 9999 = 10009998。逐位：9+9=18 出 8 进 1；9+9+1=19 出 9 进 1（连出三次 9）；第五位起 l2 已空按 0 算，9+0+1=10 出 0 进 1，再两次同样出 0 进 1；七位走完 carry 还是 1，多造一个节点 1。结果 [8,9,9,9,0,0,0,1]，与样例一致。

参考实现¶

solutions/leetcode/LC2/sol.py
from typing import List, Optional


class Solution:
    def addTwoNumbers(self, l1: "Optional[ListNode]", l2: "Optional[ListNode]") -> "Optional[ListNode]":
        # 哨兵节点：让「接第一个结果位」和「接后续结果位」写法一致，最后取 dummy.next
        dummy = ListNode(0)
        cur = dummy
        carry = 0
        # 三个条件缺一不可：两条链都走完时，carry 还可能欠着最高位那个 1
        while l1 or l2 or carry:
            # 短链走完之后按 0 补位，等价于竖式加法里高位补零对齐
            a = l1.val if l1 else 0
            b = l2.val if l2 else 0
            total = a + b + carry
            carry = total // 10          # 溢出到下一位的量；本题恒为 0 或 1
            cur.next = ListNode(total % 10)   # 本位只保留个位数字
            cur = cur.next
            # 前进前先判空：链已经走完时 l1 是 None，取 .next 会 AttributeError
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
        return dummy.next                # dummy 本身是占位的，真正的表头在它后面

LC2 两数相加¶