2. 两数相加

题目是这样的：给两个非空的链表，表示两个非负的整数。数字的每一位按逆序存储，每个节点只存一位。把两个数相加，返回一个表示和的链表，同样按逆序存储（题目出处：力扣 2 题面）。每条链的节点数在 1 到 100 之间，每个节点的值在 0 到 9 之间，除了数字 0 本身，最高位（链表末尾）不会是 0。

官方例子：[2,4,3] 加 [5,6,4] 得到 [7,0,8]，就是 342 + 465 = 807；[0] 加 [0] 得到 [0]；[9,9,9,9,9,9,9] 加 [9,9,9,9] 得到 [8,9,9,9,0,0,0,1]，就是 9999999 + 9999 = 10009998。

链表本身就是按竖式排好的

第一眼看这道题，链表好像是个障碍：加法明明是数的事，怎么给存到链表里了。反过来想，个位在链表头，高位在链表尾，从头往后走就是从个位往高位走，正好是竖式加法从右往左的顺序。题目把数字倒过来存，是把加法的顺序直接摆好了，不用先反转。

所以这道题没有“怎么把链表变成数”这一步，链表本身就是加法的算盘，每一位只看三样东西：这一位两个数字、上一位传来的进位。写下和的个位，把十位当进位传下去，走到下一位接着算。

拿官方第一个例子走一遍。342 + 465 = 807，链表是 [2,4,3] 和 [5,6,4]。第 0 位：2 + 5 + 进位 0 = 7，写下 7，新进位 0。第 1 位：4 + 6 + 进位 0 = 10，写下 0，新进位 1。第 2 位：3 + 4 + 进位 1 = 8，写下 8，新进位 0。结果 [7,0,8]。第 1 位的 0 最容易看错：4 + 6 明明是 10，写下 0 是因为满十进一，1 传到下一位去了。

最直接的做法：拼成整数再拆回来

先写最直白的：把两条链表各拼成一个整数，相加，再把结果拆回链表。Python 的整数本身没有位数上限（3.11 起整数与字符串互转默认限制 4300 位，这里只用算术，不走字符串，不受影响），这么写跑得通。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val  # 存一位数字
        self.next = next  # 指下一位


def add_naive(l1, l2):
    def to_int(node):
        n, mul = 0, 1
        while node is not None:
            n += node.val * mul  # 个位乘 1，十位乘 10，依此类推
            mul *= 10
            node = node.next
        return n
    total = to_int(l1) + to_int(l2)
    if total == 0:
        return ListNode(0)
    head = cur = None
    while total > 0:
        node = ListNode(total % 10)  # 一位一位拆回来
        total //= 10
        if head is None:
            head = cur = node
        else:
            cur.next = node
            cur = node
    return head

这份代码是对的，官方三个例子全过，3000 组随机数据和后面的正式解法对拍也没有一组失配（随机种子 20261113：先抽两条链的长度，各 1 到 10 位，再逐位抽 0 到 9，最高位抽到 0 就重抽 1 到 9）。但它绕开了这道题要练的东西：链表一位一位走、进位一位一位传。它把加法外包给了整数，自己只负责搬运。而且它依赖语言的大整数，换到没有大整数的语言就走不通；数字一长，拼整数本身也要 O(n) 的额外空间。

本地实测（Python 3.12.3，本机，单次计时）也能看出差别。2000 位加 2000 位（随机种子 7，全新的 Random(7) 用 randint 逐个生成，最高位非 0），这份做法要 0.0090 秒；位数涨到 20000 位（随机种子 7，同样做法），要 0.4802 秒。位数变成 10 倍，用时涨了约 53 倍。大整数相加不是线性的，数越长越吃亏。

正式做法：逐位相加，带一个进位

两个指针齐头并进，逐位相加，带一个进位 carry。每一位算 (a + b + carry) % 10，新的 carry 是 (a + b + carry) // 10。一条链走完了就当那位是 0；最后 carry 还剩 1，就再挂一个节点。

def add_iterative(l1, l2):
    dummy = ListNode(0)  # 哑节点，省掉“第一个节点单独处理”的判断
    cur = dummy
    carry = 0
    p, q = l1, l2
    while p is not None or q is not None or carry:
        a = p.val if p is not None else 0  # 一条链走完了，那位当 0
        b = q.val if q is not None else 0
        s = a + b + carry
        carry = s // 10   # 进位不是 0 就是 1，因为 9 + 9 + 1 = 19
        cur.next = ListNode(s % 10)  # 写下这一位的个位
        cur = cur.next
        if p is not None:
            p = p.next
        if q is not None:
            q = q.next
    return dummy.next  # 哑节点本身不是答案，从它的 next 开始

自己造一组数验一下：[6,7,8] 加 [4,5]，就是 876 + 54 = 930。第 0 位：6 + 4 + 进位 0 = 10，写下 0，新进位 1。第 1 位：7 + 5 + 进位 1 = 13，写下 3，新进位 1。第 2 位：8 + 0 + 进位 1 = 9，写下 9，新进位 0。结果 [0,3,9]。第 2 位里的 0，是短链走完后补上的：[4,5] 只有两位，第 2 位没有数字，就当 0 用。

这份代码时间是 O(max(m, n))，两条链各走一遍；额外空间 O(1)，不算返回的链表本身，只用了几个变量。本地实测，2000 位加 2000 位（随机种子 7，同样做法）只要 0.0027 秒，20000 位加 20000 位（随机种子 7，同样做法）只要 0.0336 秒。位数变成 10 倍，用时只涨了约 12 倍。20000 位的时候，朴素做法的 0.4802 秒是它的约 14 倍。

三个容易踩的坑

第一个坑是循环条件。while p is not None or q is not None or carry，carry 也要算进去。只写两条链都没走完就停，[9] 加 [1] 的最后那个 1 会丢：9 + 1 = 10，写下 0 之后进位 1 还没地方放，循环一停就没了，结果变成 [0]。多挂一个节点，结果才是 [0,1]。第三个官方例子也是这个道理：9999999 + 9999，一路进位传到最后，多出一位 1，结果是 [8,9,9,9,0,0,0,1]，不是 [8,9,9,9,0,0,0]。

第二个坑是进位最大是多少。两个一位数最大是 9 + 9，再加上进位 1，和最大是 19。所以 carry 只会是 0 或 1，不用担心进位本身又进位。s // 10 和 s % 10 一句拆出进位和本位，写成 divmod(s, 10) 也一样。

第三个坑是短链走完之后怎么办。两条链长度不一样是常事，短的那条走完了，长的那条剩下的位还要继续加进位。把走完的链当成 0 接着算就行，不用单独写一段“把剩下的抄过去”。但要注意，剩下的位不是原样抄：进位还在传，9 加进位 1 变成 0 还要再进 1。[9,9] 加 [1] 就是例子：99 + 1 = 100，结果 [0,0,1]，两个 9 都被进位翻成了 0，最后又多出一位 1。

另外几个边界不用特殊处理：[0] 加 [0] 是 [0]，不是空链表，因为循环至少跑一位；[5] 加 [5] 是 [0,1]，5 + 5 = 10；[0,0,1] 加 [9] 是 [9,0,1]，100 + 9 = 109，中间的 0 原样留着；[1] 加 [9,9,9] 是 [0,0,0,1]，1 + 999 = 1000。上面这些边界，三种解法结果一致。

递归是同一路，只是换了个写法

逐位相加也可以写成递归：这一位算完，把“下一位”交给下一层调用。思路和迭代版一模一样，代码还短一点。

def add_recursive(l1, l2, carry=0):
    if l1 is None and l2 is None:
        return ListNode(1) if carry else None  # 链走完了，进位还在就再挂一个节点
    a = l1.val if l1 is not None else 0
    b = l2.val if l2 is not None else 0
    s = a + b + carry
    node = ListNode(s % 10)
    node.next = add_recursive(
        l1.next if l1 is not None else None,
        l2.next if l2 is not None else None,
        s // 10,
    )
    return node

递归版时间一样是 O(max(m, n))，但额外空间是递归栈 O(max(m, n))，链表一长就多一层调用。本地实测，200 位加 200 位（随机种子 7，同样做法）只要 0.0003 秒，和迭代版结果一致；但 2000 位直接报 RecursionError（maximum recursion depth exceeded），默认递归上限约 1000 层。题目约束每条链最多 100 位，递归在题目范围内没问题，可链一长就撞上限，迭代没有这个问题。两种写法选哪个，看链有多长。

复杂度再算一遍

朴素版：时间 O(n²)，拼整数和拆回链表时，每一步都要处理已经攒到 O(n) 位的大整数；额外空间 O(n)，拼出来的大整数本身。迭代版：时间 O(max(m, n))，两条链各走一遍；额外空间 O(1)，不算返回的链表本身。递归版：时间 O(max(m, n))；额外空间 O(max(m, n))，递归栈。

从朴素到迭代，时间省了，做法也顺了：加法回到了链表该在的位置，从个位起，一位算完再算下一位，进位跟着往下传。