大家好，我是 @负雪明烛。

「求加法」是个系列题目，类似的题目见文末。

解题方法：模拟法

十进制加法

我们先回顾一下十进制加法的计算过程：

2. 两数相加 - 图1

使用「竖式」计算十进制的加法的方式：

  1. 两个「加数」的右端对齐；
  2. 从最右侧开始，依次计算对应的两位数字的和。如果和大于等于 10，则把和的个位数字计入结果，并向前面进位。
  3. 依次向左计算对应位置两位数字的和，如果有进位需要加上进位。如果和大于等于 10，仍然把和的个位数字计入结果，并向前面进位。
  4. 当两个「加数」的每个位置都计算完成，如果最后仍有进位，需要把进位数字保留到计算结果中。

链表相加

本题中的两个链表表示的数字是个位在前，高位在后。

所以，我们可以从两个链表的开头开始同时向后遍历，模拟上面加法的过程。图源。

2. 两数相加 - 图2

可以用两种做法：循环 + 递归。

在实现中需要注意的有：

  1. 不可以把链表先转化成 int 型数字再求和，因为可能溢出；
  2. 两个「加数」的字符串长度可能不同；
  3. 在最后，如果进位 carry 不为 0，那么最后需要计算进位；

方法一：循环

循环的思想比较朴素，就是两个指针同时遍历两个链表每个节点并相加的过程。

代码中的巧妙之处：

  1. while (i >= 0 || j >= 0 || carry != 0)含义：
    1. 链表 a 和 b 只要有一个没遍历完，那么就继续遍历；
    2. 如果链表 a 和 b 都遍历完了，但是最后留下的进位 carry != 0，那么需要把进位也保留到结果中。
  2. 取 digit 的时候，如果链表 a 和 b 中有一个已经遍历完了（即 2. 两数相加 - 图3 或者 2. 两数相加 - 图4），则认为 a 和 b 的对应位置是 2. 两数相加 - 图5 。

Java / C++ / Python 三种语言的代码：

  1. class Solution {
  2.     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
  3.         ListNode dummy = new ListNode(0);
  4.         ListNode cur = dummy;
  5.         int carry = 0;
  6.         while (l1 != null || l2 != null || carry != 0) {
  7.             int i1 = l1 != null ? l1.val : 0;
  8.             int i2 = l2 != null ? l2.val : 0;
  9.             int add = i1 + i2 + carry;
  10.             carry = add >= 10 ? 1 : 0;
  11.             add = add >= 10 ? add - 10 : add;
  12.             cur.next = new ListNode(add);
  13.             cur = cur.next;
  14.             if (l1 != null)
  15.                 l1 = l1.next;
  16.             if (l2 != null)
  17.                 l2 = l2.next;
  18.         }
  19.         return dummy.next;
  20.     }
  21. }
  1. class Solution {
  2. public:
  3.     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
  4.         ListNode* dummy = new ListNode(0);
  5.         ListNode* cur = dummy;
  6.         int carry = 0;
  7.         while (l1 || l2 || carry) {
  8.             int i1 = l1 ? l1->val : 0;
  9.             int i2 = l2 ? l2->val : 0;
  10.             int add = i1 + i2 + carry;
  11.             carry = add >= 10 ? 1 : 0;
  12.             add = add >= 10 ? add - 10 : add;
  13.             cur->next = new ListNode(add);
  14.             cur = cur->next;
  15.             if (l1)
  16.                 l1 = l1->next;
  17.             if (l2)
  18.                 l2 = l2->next;
  19.         }
  20.         return dummy->next;
  21.     }
  22. };
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        dummy = ListNode(0)
        cur = dummy
        carry = 0
        while l1 or l2 or carry:
            i1 = l1.val if l1 else 0
            i2 = l2.val if l2 else 0
            add = i1 + i2 + carry
            carry = 1 if add >= 10 else 0
            add = add - 10 if add >= 10 else add
            cur.next = ListNode(add)
            cur = cur.next
            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next
        return dummy.next

复杂度分析：

  • 时间复杂度：2. 两数相加 - 图6)#card=math&code=O%28max%28M%2C%20N%29%29&id=XQ79I)，2. 两数相加 - 图7 和 2. 两数相加 - 图8 分别是链表 a 和 b 的长度；
  • 空间复杂度：2. 两数相加 - 图9#card=math&code=O%281%29&id=t3gE3)，只使用了常数的空间。

方法二：递归

递归解法非常巧妙。

做递归题目一定要牢记「递归函数的定义」。

递归函数定义：addTwoNumbers 表示将两个链表 l1 和 l2 相加得到的新链表；
递归终止条件：如果 l1 和 l2 有一个为空，则返回另外一个。
递归函数内容：

  • 把两个链表节点的值相加（结果记为 add ）。把 add 模 2. 两数相加 - 图10 作为当前的链表节点的值。
  • 把两个链表的 next 节点相加。（注意：如果当前相加的结果 $add >= 10$，需要把 $next$ 节点相加得到的结果 + 1。）

递归解法妙在天然地处理好了两个链表不一样长、最终相加结果有进位的情况。

Java / C++ / Python 三种语言的代码：

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null)
            return l2;
        if (l2 == null)
            return l1;
        int add = l1.val + l2.val;
        ListNode res = new ListNode(add % 10);
        res.next = addTwoNumbers(l1.next, l2.next);
        if (add >= 10)
            res.next = addTwoNumbers(res.next, new ListNode(1));
        return res;
    }
}

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;
        int target = l1->val + l2->val;
        ListNode* res = new ListNode(target % 10);
        res->next = addTwoNumbers(l1->next, l2->next);
        if (target >= 10)
            res->next = addTwoNumbers(res->next, new ListNode(1));
        delete l1, l2;
        return res;
    }
};

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        if not l1:
            return l2
        if not l2:
            return l1
        add = l1.val + l2.val
        res = ListNode(add % 10)
        res.next = self.addTwoNumbers(l1.next, l2.next)
        if add >= 10:
            res.next = self.addTwoNumbers(res.next, ListNode(1))
        return res

类似题目

看完本题解本题，你可以解决以下题目：

总结

  1. 「加法」系列题目都不难，其实就是 「列竖式」模拟法。
  2. 需要注意的是 while循环结束条件，注意遍历两个「加数」不要越界，以及进位。

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。