秋招知识库

主题

题目链接 · 灵神原题解（署名来源）

方法一：递归 ​

<lc2-1.png,lc2-2.png,lc2-3.png,lc2-4.png,lc2-5.png,lc2-6.png,lc2-7.png,lc2-8.png>

把虚线内要计算的内容，可以理解为一个和原问题相似的，规模更小的子问题，所以非常适合用递归解决。

每次把两个节点值 l1.val, l2.val 与进位值 carry 相加，除以 10 的余数即为当前节点需要保存的数位，除以 10 的商即为新的进位值。

一遇到递归就头晕？请看【基础算法精讲 09】。

不了解链表的同学请看【基础算法精讲 06】。

写法一：创建新节点 ​

python
class Solution:
    # l1 和 l2 为当前遍历的节点，carry 为进位
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode], carry=0) -> Optional[ListNode]:
        if l1 is None and l2 is None and carry == 0:  # 递归边界
            return None

        s = carry
        if l1:
            s += l1.val  # 累加进位与节点值
            l1 = l1.next
        if l2:
            s += l2.val
            l2 = l2.next

        # s 除以 10 的余数为当前节点值，商为进位
        return ListNode(s % 10, self.addTwoNumbers(l1, l2, s // 10))
cpp
// C++ 版待补充
cpp
class Solution {
public:
    // l1 和 l2 为当前遍历的节点，carry 为进位
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2, int carry = 0) {
        if (l1 == nullptr && l2 == nullptr && carry == 0) { // 递归边界
            return nullptr;
        }

        int s = carry;
        if (l1) {
            s += l1->val; // 累加进位与节点值
            l1 = l1->next;
        }
        if (l2) {
            s += l2->val;
            l2 = l2->next;
        }

        // s 除以 10 的余数为当前节点值，商为进位
        return new ListNode(s % 10, addTwoNumbers(l1, l2, s / 10));
    }
};

写法二：原地修改 ​

代码实现时，有一个简化代码的小技巧：如果递归中发现 l2 的长度比 l1 更长，那么可以交换 l1 和 l2，保证 l1 不是空节点，从而简化代码逻辑。

python
class Solution:
    # l1 和 l2 为当前遍历的节点，carry 为进位
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode], carry=0) -> Optional[ListNode]:
        if l1 is None and l2 is None:  # 递归边界
            return ListNode(carry) if carry else None  # 如果进位了，就额外创建一个节点
        if l1 is None:  # 如果 l1 是空的，那么此时 l2 一定不是空节点
            l1, l2 = l2, l1  # 交换 l1 与 l2，保证 l1 非空，从而简化代码
        s = carry + l1.val + (l2.val if l2 else 0)  # 节点值和进位加在一起
        l1.val = s % 10  # 每个节点保存一个数位（直接修改原链表）
        l1.next = self.addTwoNumbers(l1.next, l2.next if l2 else None, s // 10)  # 进位
        return l1
cpp
// C++ 版待补充
cpp
class Solution {
public:
    // l1 和 l2 为当前遍历的节点，carry 为进位
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2, int carry = 0) {
        if (l1 == nullptr && l2 == nullptr) { // 递归边界
            return carry ? new ListNode(carry) : nullptr; // 如果进位了，就额外创建一个节点
        }
        if (l1 == nullptr) { // 如果 l1 是空的，那么此时 l2 一定不是空节点
            swap(l1, l2); // 交换 l1 与 l2，保证 l1 非空，从而简化代码
        }
        int sum = carry + l1->val + (l2 ? l2->val : 0); // 节点值和进位加在一起
        l1->val = sum % 10; // 每个节点保存一个数位（直接修改原链表）
        l1->next = addTwoNumbers(l1->next, (l2 ? l2->next : nullptr), sum / 10); // 进位
        return l1;
    }
};

复杂度分析 ​

  • 时间复杂度：O(n)，其中 n 为 l1 长度和 l2 长度的最大值。
  • 空间复杂度：O(n)。递归需要 O(n) 的栈空间。

方法二：迭代 ​

首先请看如何遍历一个链表，代码框架如下：

python
# 遍历链表 l1
while l1:  # 从链表头节点开始向后遍历，直到遇到空节点
    print(l1.val)  # 当前节点值
    l1 = l1.next  # 准备遍历下一个节点
cpp
// C++ 版待补充
cpp
// 遍历链表 l1
while (l1) { // 从链表头节点开始向后遍历，直到遇到空节点
    cout << l1->val << endl; // 当前节点值
    l1 = l1->next; // 准备遍历下一个节点
}

迭代的思路是，初始化答案为一个「空链表」，每次循环，向该链表末尾添加一个节点（保存一个数位）。

循环即遍历链表 l1 和 l2，每次把两个节点值 l1.val, l2.val 与进位值 carry 相加，除以 10 的余数即为当前节点需要保存的数位，除以 10 的商即为新的进位值。

需要注意的是，在第一次循环时，我们无法往一个空节点的末尾添加节点。这里的技巧是，创建一个哨兵节点（dummy node），当成初始的「空链表」。循环结束后，哨兵节点的下一个节点就是最终要返回的链表头节点。

python
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        cur = dummy = ListNode()  # 哨兵节点
        carry = 0  # 进位值
        while l1 or l2 or carry:  # 有一个不是空节点，或者还有进位，就继续迭代
            s = carry
            if l1:
                s += l1.val  # 节点值和进位加在一起
                l1 = l1.next  # 下一个节点
            if l2:
                s += l2.val  # 节点值和进位加在一起
                l2 = l2.next  # 下一个节点
            cur.next = ListNode(s % 10)  # 每个节点保存一个数位
            carry = s // 10  # 新的进位
            cur = cur.next  # 下一个节点
        return dummy.next  # 哨兵节点的下一个节点就是头节点
cpp
// C++ 版待补充
cpp
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode dummy; // 哨兵节点
        ListNode* cur = &dummy;
        int carry = 0; // 进位值
        while (l1 || l2 || carry) { // 有一个不是空节点，或者还有进位，就继续迭代
            int sum = carry;
            if (l1) {
                sum += l1->val; // 节点值和进位加在一起
                l1 = l1->next; // 下一个节点
            }
            if (l2) {
                sum += l2->val; // 节点值和进位加在一起
                l2 = l2->next; // 下一个节点
            }  
            cur = cur->next = new ListNode(sum % 10); // 每个节点保存一个数位
            carry = sum / 10; // 新的进位
        }
        return dummy.next; // 哨兵节点的下一个节点就是头节点
    }
};

复杂度分析 ​

  • 时间复杂度：O(n)，其中 n 为 l1 的长度和 l2 的长度的最大值。
  • 空间复杂度：O(1)。返回值不计入。

思考题 ​

本题的链表是从数字的最低位开始的，如果改成从最高位开始，要怎么做呢？

更多链表题目，见下面的链表题单。

分类题单 ​

如何科学刷题？

  1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
  2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
  3. 单调栈（基础/矩形面积/贡献法/最小字典序）
  4. 网格图（DFS/BFS/综合应用）
  5. 位运算（基础/性质/拆位/试填/恒等式/思维）
  6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
  7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
  8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
  9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
  10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
  11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
  12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

本文整理自灵茶山艾府（endlesscheng）的公开内容，仅供个人学习使用
本站为个人秋招复习知识库 · 仅供个人学习使用

本站仅供个人学习使用，请勿外传

秋招知识库