LeetCode 2. 两数相加

◎

本节目标

沿逆序数字链表逐位相加，用进位状态构造结果链表。

查看 LeetCode 原题

题意与边界

两条非空链表按低位到高位保存两个非负整数，每个节点是一位数字。返回同样按逆序保存的和；两条链表长度可以不同，最高位相加后还可能产生新进位。

逐位加法状态

哨兵节点让结果头部和后续节点使用同一套追加逻辑。每轮从 carry 开始，分别加入当前仍存在的两个数字，当前结果位是总和对 10 取模，新进位是整除 10。只要任一链表未结束或进位不为零，循环就必须继续。

正确性依据

处理第 i 轮前，结果链表已经正确保存低 i 位，carry 恰好是这些位向更高一位产生的进位。本轮加入两个整数的第 i 位后，取模得到当前位、整除得到下一轮进位，保持该不变量。循环结束时不存在未处理数字和进位，因此结果表示完整的和。

代码实现

C++

C++17

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode dummy;
        ListNode* tail = &dummy;
        int carry = 0;
        while (l1 != nullptr || l2 != nullptr || carry != 0) {
            int sum = carry;
            if (l1 != nullptr) {
                sum += l1->val;
                l1 = l1->next;
            }
            if (l2 != nullptr) {
                sum += l2->val;
                l2 = l2->next;
            }
            tail->next = new ListNode(sum % 10);
            tail = tail->next;
            carry = sum / 10;
        }
        return dummy.next;
    }
};

Python

Python 3

from typing import Optional


class Solution:
    def addTwoNumbers(
        self,
        l1: Optional[ListNode],
        l2: Optional[ListNode],
    ) -> Optional[ListNode]:
        dummy = ListNode()
        tail = dummy
        carry = 0
        while l1 is not None or l2 is not None or carry != 0:
            total = carry
            if l1 is not None:
                total += l1.val
                l1 = l1.next
            if l2 is not None:
                total += l2.val
                l2 = l2.next
            tail.next = ListNode(total % 10)
            tail = tail.next
            carry = total // 10
        return dummy.next

复杂度分析

• 时间复杂度：O(max(m, n))。
• 空间复杂度：O(max(m, n))，用于结果链表；除结果外只使用常数状态。

易错点

• 只在两条链表都非空时循环，遗漏较长链表的剩余位。
• 忘记循环结束后的最高位进位。
• 把逆序存储误当成从最高位开始处理，额外引入不必要的反转。

模式迁移

把进位或借位作为跨位置的有限状态，可以统一处理链式大整数加法、字符串加法和多进制逐位运算。