leetcode445. 两数相加 II

leetcode445. 两数相加 II

五月 23, 2020

leetcode445. 两数相加 II

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

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

进阶：
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

示例：
输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7

用栈存储两个链表的节点，这样出来的时候就都是最低位了。然后在考虑进位的情况。
代码冗余部分很多，但是理解简单。

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
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();
        while (l1 != null) {
            s1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            s2.push(l2.val);
            l2 = l2.next;
        }
        int cf = 0;//cf表示进位是多少
        ListNode head = new ListNode(0);//最后返回的链表的头结点，这个链表头结点不变动，最后返回head.next
        ListNode tmp = null;
        while (!s1.isEmpty() && !s2.isEmpty()) {
            int n1 = s1.pop();
            int n2 = s2.pop();
            int val = n1 + n2 +cf;
            cf = val / 10;
            val %= 10;
            tmp = head.next;
            head.next = new ListNode(val);
            head.next.next = tmp;
        }
        if (!s1.isEmpty()) {
            while (!s1.isEmpty()) {
                int val = s1.pop() + cf;
                cf = val / 10;
                val %= 10;
                tmp = head.next;
                head.next = new ListNode(val);
                head.next.next = tmp;
            }
        }
        if (!s2.isEmpty()) {
            while (!s2.isEmpty()) {
                int val = s2.pop() + cf;
                cf = val / 10;
                val %= 10;
                tmp = head.next;
                head.next = new ListNode(val);
                head.next.next = tmp;
            }
        }
        if (cf != 0) {//最后还有进位，表示多出来一位，比如[5],[5]
            tmp = head.next;
            head.next = new ListNode(cf);
            head.next.next = tmp;
        }
        return head.next;
    }

leetcode 79/100