vvrf / DSA.log

问题拆解

两个非负整数按逆序存在链表里（个位在表头），求和后同样以逆序链表返回。逆序看着别扭，其实是出题人递的台阶：竖式加法本来就从个位算起，逆序存储让两条链表从表头开始就是低位对齐的，顺着走一遍、带着进位，就是小学竖式的机械翻译。要是先把链表转成整数再相加，链表长达 100 位，早就超出任何原生整数类型了。

真正要处理干净的是三件事的收尾：两条链表长度可能不同（短的一方走完后按 0 计）；算到最后进位可能还剩 1（如 999 + 1，结果比两个输入都长一位）；结果表头没有前驱。

把循环条件写成 l1 || l2 || carry：任何一方还有数字、或者还压着进位，就继续造节点。三种“还没完”的情形统一成一个条件，最高位进位不再是特例。

dummy + 进位变量

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode();
    ListNode tail = 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;
        tail.next = new ListNode(sum % 10);
        tail = tail.next;
    }
    return dummy.next;
}

def addTwoNumbers(l1, l2):
    dummy = ListNode()
    tail = dummy
    carry = 0
    while l1 or l2 or carry:
        total = carry
        if l1:
            total += l1.val
            l1 = l1.next
        if l2:
            total += l2.val
            l2 = l2.next
        carry, digit = divmod(total, 10)
        tail.next = ListNode(digit)
        tail = tail.next
    return dummy.next

func addTwoNumbers(l1, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    tail := dummy
    carry := 0
    for l1 != nil || l2 != nil || carry != 0 {
        sum := carry
        if l1 != nil {
            sum += l1.Val
            l1 = l1.Next
        }
        if l2 != nil {
            sum += l2.Val
            l2 = l2.Next
        }
        carry = sum / 10
        tail.Next = &ListNode{Val: sum % 10}
        tail = tail.Next
    }
    return dummy.Next
}

pub fn add_two_numbers(
    mut l1: Option<Box<ListNode>>,
    mut l2: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
    let mut dummy = Box::new(ListNode::new(0));
    let mut tail = &mut dummy;
    let mut carry = 0;
    while l1.is_some() || l2.is_some() || carry != 0 {
        let mut sum = carry;
        if let Some(node) = l1 {
            sum += node.val;
            l1 = node.next; // 取走当前位，指针前移
        }
        if let Some(node) = l2 {
            sum += node.val;
            l2 = node.next;
        }
        carry = sum / 10;
        tail.next = Some(Box::new(ListNode::new(sum % 10)));
        tail = tail.next.as_mut().unwrap();
    }
    dummy.next
}

每轮的和最多是 9 + 9 + 1 = 19，所以 carry 只会是 0 或 1，sum % 10 和 sum / 10 一次拆出本位与进位。dummy 假头让第一个节点和后面的节点走同一条“接在 tail 后面”的路径，返回时跳过它即可。

最常见的错误是把循环条件写成 l1 && l2，再对剩余部分单独补一段循环、末尾再补一个进位判断——三段代码三处边界。而 l1 || l2 || carry 把“短链按 0 补齐”和“最高位进位多出一节”都吸进了主循环：走空的链表贡献 0，最后剩的 carry == 1 会让循环多跑一轮、恰好造出那个多出来的最高位节点。

复杂度

指标	复杂度	原因
时间	`O(max(m, n))`	两条链表各走一遍，最多多造一个进位节点
空间	`O(1)`	除结果链表外只用 carry 和几个指针

可以迁移的模式

大数、按位运算类题目，用一个 carry 变量贯穿循环，而不是最后补丁式处理进位；
循环条件把所有“还有活没干完”的来源用或连接，边界就消失在主流程里；
构建新链表照例挂 dummy，首节点不特殊。

同样的骨架直接适用于二进制求和（67）、链表加一（369）；如果数字是正序存储（445），先用栈把顺序倒过来，核心循环一行不改。