2. Add Two Numbers 两数相加 | 弟弟快看-教程

两数相加，链表，求加法，题解，leetcode, 力扣，python, c++, java

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

题目描述

Youare 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.

Youmay 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.

题目大意

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

解题方法

十进制加法

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

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

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

链表相加

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

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

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

在实现中需要注意的有：

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

方法一：循环

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

代码中的巧妙之处：

1、 while(i>=0||j>=0||carry!=0)含义：

1、链表a和b只要有一个没遍历完，那么就继续遍历；
2、如果链表a和b都遍历完了，但是最后留下的进位carry!=0，那么需要把进位也保留到结果中；
2、取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;
    }
}

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

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;
    }
};

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

复杂度分析：

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

方法二：递归

递归解法非常巧妙。

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

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

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

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

Java 代码如下：

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;
    }
}

1 2 3 4 5 6 7 8 9 10 11 12 13 14

C++代码如下：

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;
    }
};

1 2 3 4 5 6 7 8 9 10 11 12 13 14

Python 代码如下：

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 3 4 5 6 7 8 9 10 11 12

类似题目

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

[2. 两数相加open in new window][2. _open in new window]
445. 两数相加 IIopen in new window
67. 二进制求和open in new window
415. 字符串相加open in new window
66. 加一open in new window
989. 数组形式的整数加法open in new window

总结

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

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛授权发布，任何组织或个人未经作者授权不得转发