2. Add Two Numbers 两数相加

作者：负雪明烛 id： fuxuemingzhu 个人博客： https://fuxuemingzhu.cn/ 个人公众号：负雪明烛本文关键词：两数相加，链表，求加法，题解，leetcode, 力扣，python, c++, java

题目地址：https://leetcode.com/problems/add-two-numbers/description/

题目描述

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

题目大意

有两个链表，分别是逆序了的十进制数字。现在要求两个十位数字的和，要求返回的结果也是链表。

解题方法

十进制加法

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

加法.001.jpeg

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

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

链表相加

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

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

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

在实现中需要注意的有：

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

方法一：循环

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

代码中的巧妙之处：

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

Java 代码如下：

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
            int i1 = l1 != null ? l1.val : 0;
            int i2 = l2 != null ? l2.val : 0;
            int add = i1 + i2 + carry;
            carry = add >= 10 ? 1 : 0;
            add = add >= 10 ? add - 10 : add;
            cur.next = new ListNode(add);
            cur = cur.next;
            if (l1 != null)
                l1 = l1.next;
            if (l2 != null)
                l2 = l2.next;
        }
        return dummy.next;
    }
}

C++ 代码如下：

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        int carry = 0;
        while (l1 || l2 || carry) {
            int i1 = l1 ? l1->val : 0;
            int i2 = l2 ? l2->val : 0;
            int add = i1 + i2 + carry;
            carry = add >= 10 ? 1 : 0;
            add = add >= 10 ? add - 10 : add;
            cur->next = new ListNode(add);
            cur = cur->next;
            if (l1)
                l1 = l1->next;
            if (l2)
                l2 = l2->next;
        }
        return dummy->next;
    }
};

Python 代码如下：

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

复杂度分析：

时间复杂度：$O(max(M, N))$，$M$ 和 $N$ 分别是链表 a 和 b 的长度；
空间复杂度：$O(1)$，只使用了常数的空间。

方法二：递归

递归解法非常巧妙。

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

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

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

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