一【题目类别】

• 栈

二【题目难度】

• 中等

三【题目编号】

• 445.两数相加 II

四【题目描述】

• 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
• 你可以假设除了数字 0 之外，这两个数字都不会以零开头。

五【题目示例】

• 示例1：
  

  • 输入：l1 = [7,2,4,3], l2 = [5,6,4]
  • 输出：[7,8,0,7]

• 示例2：

  • 输入：l1 = [2,4,3], l2 = [5,6,4]
  • 输出：[8,0,7]

• 示例3：

  • 输入：l1 = [0], l2 = [0]
  • 输出：[0]

六【题目提示】

• 链表的长度范围为 [1, 100]
• 0 <= node.val <= 9
• 输入数据保证链表代表的数字无前导 0

七【题目进阶】

• 如果输入链表不能翻转该如何解决？

八【解题思路】

• 利用栈的思想
• 因为要从低位开始相加，所以将两个链表元素值入栈
• 然后从低位开始相加，记录进位，每次得到一个结果就将链表连接起来
• 还要注意的是两个链表长度可能不一样，那么短的就认为加0即可
• 最后返回链表头结点即可

九【时间频度】

• 时间复杂度：$O(max(m,n))$，其中 $m,n$ 是链表元素长度
• 空间复杂度：$O(m+n)$，其中 $m,n$ 是链表元素长度

十【代码实现】

1. Java语言版

package Stack;

import java.util.ArrayDeque;
import java.util.Deque;

public class p445_AddingTwoNumbersII {

    int val;
    p445_AddingTwoNumbersII next;

    public p445_AddingTwoNumbersII(int val) {
        this.val = val;
    }

    public p445_AddingTwoNumbersII(int val, p445_AddingTwoNumbersII next) {
        this.val = val;
        this.next = next;
    }

    public static void main(String[] args) {
        p445_AddingTwoNumbersII l11 = new p445_AddingTwoNumbersII(7);
        p445_AddingTwoNumbersII l12 = new p445_AddingTwoNumbersII(2);
        p445_AddingTwoNumbersII l13 = new p445_AddingTwoNumbersII(4);
        p445_AddingTwoNumbersII l14 = new p445_AddingTwoNumbersII(3);
        p445_AddingTwoNumbersII l21 = new p445_AddingTwoNumbersII(5);
        p445_AddingTwoNumbersII l22 = new p445_AddingTwoNumbersII(6);
        p445_AddingTwoNumbersII l23 = new p445_AddingTwoNumbersII(4);
        l11.next = l12;
        l12.next = l13;
        l13.next = l14;
        l21.next = l22;
        l22.next = l23;
        p445_AddingTwoNumbersII res = addTwoNumbers(l11, l21);
        while (res != null) {
            if (res.next != null) {
                System.out.print(res.val + "->");
            } else {
                System.out.print(res.val);
            }
            res = res.next;
        }
    }

    public static p445_AddingTwoNumbersII addTwoNumbers(p445_AddingTwoNumbersII l1, p445_AddingTwoNumbersII l2) {
        Deque<Integer> stack1 = new ArrayDeque<Integer>();
        Deque<Integer> stack2 = new ArrayDeque<Integer>();
        int carry = 0;
        p445_AddingTwoNumbersII head = null;
        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
            int x = stack1.isEmpty() ? 0 : stack1.pop();
            int y = stack2.isEmpty() ? 0 : stack2.pop();
            int sum = x + y + carry;
            carry = sum / 10;
            p445_AddingTwoNumbersII temp = new p445_AddingTwoNumbersII(sum % 10);
            temp.next = head;
            head = temp;
        }
        return head;
    }

}
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
59
60
61
62
63
64
65
66
67
68
69

2. C语言版

#include
#include

struct ListNode {
	int val;
	struct ListNode *next;
};

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{
	int stack1[101] = { 0 };
	int stack2[101] = { 0 };
	int top1 = 0;
	int top2 = 0;
	int carry = 0;
	struct ListNode* temp = NULL;
	struct ListNode* head = NULL;
	while (l1 != NULL)
	{
		stack1[top1++] = l1->val;
		l1 = l1->next;
	}
	while (l2 != NULL)
	{
		stack2[top2++] = l2->val;
		l2 = l2->next;
	}
	while (top1 != 0 || top2 != 0 || carry != 0)
	{
		int x = top1 > 0 ? stack1[--top1] : 0;
		int y = top2 > 0 ? stack2[--top2] : 0;
		int sum = x + y + carry;
		carry = sum / 10;
		head = (struct ListNode*)malloc(sizeof(struct ListNode));
		head->val = sum % 10;
		head->next = temp;
		temp = head;
	}
	return head;
}

/*主函数省略*/
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

十一【提交结果】

1. Java语言版
   

2. C语言版