# 2.两数相加

# 题目

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
{
  "val": 2,
  "next": {
    "val": 4,
    "next": {
      "val": 3,
      "next": null
    }
  }
}
输出：7 -> 0 -> 8
原因：342 + 465 = 807

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

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    // do some things...
};

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

# 题解方法

题目：两数相加
参数：
- l1: ListNode
- l2: ListNode
结果：
- ListNode
重点：
- 两个链表参数都是非空的（不必判空）
- 代表的是两个非负的整数（不必考虑负数相加）
- 逆序（头结点为个位）
- 每个节点只有一位数
- 返回一个新的链表表示他们的和

下面是我提供或搜集的解法:

# 解法一：递归法

整体思路分两步，第一步递归将链表中对应的数相加，第二步检查是否有进位

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* list = func(l1,l2);
        check(list);
        return list;
    }
    
    ListNode* func(ListNode* l1, ListNode* l2){
        ListNode* list = new ListNode(0);
        if(!l1){
            list->val=l2->val;
            if(!l2->next)
                return list;
            else
                list->next = func(nullptr,l2->next);
        }
        if(!l2){
            list->val = l1->val;
            if(!l1->next)
                return list;
            else
                list->next = func(l1->next,nullptr);
        }
        if(l1&&l2){
            list->val = l1->val+l2->val;
            if(!l1->next&&!l2->next)
                return list;
        
        if(l1->next&&l2->next)
                list->next = func(l1->next,l2->next);
        else {
            if(!l1->next)
            list->next = func(nullptr,l2->next);
            if(!l2->next)
                list->next = func(l1->next,nullptr);
        }
        }

        return list;
    }
    void check(ListNode* list){
       if(list->next){
           if(list->val>=10){
               list->val-=10;
               list->next->val++;
           }
           check(list->next);
        }
        if(!list->next){
            if(list->val>=10){
                list->val-=10;
                list->next = new ListNode(1);
                return;
            }
        }
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

最麻烦的是两个数位数不相同，会多出很多分支。当两个数位数相同时，直接先加第一位，然后递归到底，如果两个数位数不同，则使用nullptr代替短的链表以便识别。检查是否溢出只要注意最高位的进位需要多创建一个节点就好了

递归法确实不算简单而且会有极大的内存占用，应该尝试一下是否可优化。我个人还是比较喜欢下面的这种解法。

# 解法二：双指针，堆栈空间法

# 思路

这是两个单链表，一个数字的逆序排列。所以第一位就是个位数，next为十位数... 依次类推。

输出一个链表，使用while遍历，通过两个链表的指针向下寻找，直到两个指针全部为null并且进一位为0的时候停止;

# 代码

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var twoSum = function(l1, l2) {
    // 创建一个head节点，return的时候矫正，即取head节点的next节点
    var head = new ListNode(0);
    var s = head;

    // 初始化两个指针 指向对应节点
    var pointer1 = l1;
    var pointer2 = l2;

    // 定义进一位的数
    var add = 0;

    // 存在节点或者进一位就一直向下遍历
    while(pointer1 || pointer2 || add) {
        // 定义需要相加的值
        var value1 = pointer1 ? pointer1.val : 0;
        var value2 = pointer2 ? pointer2.val : 0;

        // 得到sum结果
        var sum = value1 + value2 + add;
        add = sum / 10 | 0;
        sum = sum % 10;

        // 移动指针 如果已经到终点的忽略
        pointer1 = pointer1 && pointer1.next;
        pointer2 = pointer2 && pointer2.next;
        
        // 创建结果并加入next
        var child = new ListNode(sum);
        s.next = child;
        s = s.next;
        (!pointer1 && !pointer2) && (s.next = null) ;
    }
    // 矫正
    result = head.next;
    // 删除头节点
    delete head;
    return result;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

# 致谢

感谢大家阅读我的文章，如果对我感兴趣可以点击页面右上角，帮我点个star。

作者：前端小然子

链接： https://xiaoranzife.com/guide/arithmetic/2.AddTwoNumbers.html

来源：前端小然子的博客

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

← 1.两数之和 3.无重复字符的最长子串 →