链表十进制大数加法：进位、长度差与输入顺序

题目重点：一节点一位，训练明确低位在前，输出新链表不改输入。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

非负整数、digit为0..9整数、最低位在头；链表有限无环。题目完整位序未给，反序版本另讨论。
None视0，输出至少一个0节点；不转换成整个大整数作为实现。

解题路线

两游标逐位取x/y，缺失位按0，carry与digit由divmod(x+y+carry,10)得到。
循环条件包含carry，确保末尾1不会丢。新节点接tail，输入指针只前进不改内容。
最高位在头时可先用两个栈再从末位处理，或者反转输入但须规定是否允许修改/恢复。不能直接把同代码当两种位序通用。

手动走一遍

[9,9]+[1]即99+1：第一位10写0进1，第二位10写0进1，最后写1，输出[0,0,1]。None+None返回[0]；两侧长度不同仍按缺位0处理。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from dataclasses import dataclass


@dataclass
class Node:
    digit:int
    next:object=None


def add(a,b):
    dummy=tail=Node(0);carry=0
    while a is not None or b is not None or carry:
        x=a.digit if a is not None else 0;y=b.digit if b is not None else 0
        if type(x) is not int or type(y) is not int or not 0<=x<=9 or not 0<=y<=9:raise ValueError("decimal digits required")
        carry,digit=divmod(x+y+carry,10)
        tail.next=Node(digit);tail=tail.next
        a=a.next if a is not None else None;b=b.next if b is not None else None
    return dummy.next if dummy.next is not None else Node(0)

复杂度

O(max(m,n))时间、新结果O(max(m,n)+1)节点，除结果O(1)游标。检查环若必要需另加验证，不能无限循环。

易错点与追问

容易失分的边界

循环只在a或b存在时结束会丢最终进位。
把字符串表示输入和链表digit混用会改变位序。

继续深挖

负数要怎样比较绝对值并选择加或减？
不允许额外输出节点、必须在某条链上修改时有哪些别名风险？