【LeetCode刷题】2两数相加

2. 两数相加

JAVA代码

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
1
2
3

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]
1
2

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
1
2

提示：

• 每个链表中的节点数在范围 [1, 100] 内
• 0 <= Node.val <= 9
• 题目数据保证列表表示的数字不含前导零

方法一：模拟

初等数学

• 我们使用变量来跟踪进位，并从包含最低有效位的表头开始模拟逐位相加的过程。
• 对两数相加方法的可视化:342+465 = 807，每个结点都包含一个数字，并且数字按位逆序存储。

复杂度分析

• 时间复杂度:O(max(m,n))，假设m和n分别表示$1_1$和$1_2$的长度，上面的算法最多重复max(m，n)次
• 空间复杂度:O(max(m, n))，新列表的长度最多为max(m,n) + 1

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
1
2
3
4
5
6
7

这里leetcode直接给出了链表定义方式，自己写千万知道咋写。这边给出了多种构造方法，方便使用。

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;
        int carry = 0; //进位
        while (l1 != null || l2 != null) {
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1 + n2 + carry;
            if (head == null) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry > 0) {
            tail.next = new ListNode(carry);
        }
        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

这边看下代码，这是官网给出的答案。
在方法中，首先定义了一个ListNode head和ListNode tail，定义进位为carry=0。
当l1和l2有一个不为空时，进行循环遍历，当l1不为空的时候，将l1的值赋给n1，如果为空的话，则给n1赋0，n1就是当前指针指向的值，同理，对于l2也定义一个n2，用来存放当前指针指向的值。sum就是加的和。这里为什么加上进位？例子342+465 = 807，当我们进行4+6=10，有一个进位carry=1，这个1需要加给下一个指针指向的值。
如果head为空，则将head和tail都赋值为当前加的和sum；否则，就将当前的sun存入到尾指针中，尾指针在指向下一个。进位为sum的十位上的数，通过整除10获得；如果l1和l2不为空，指针就接着指向下一个。如此循环，直到循环当前l1和l2都为空结束循环。
如果最后的进位carry大于0，想象一下56+53=109，指针逆着算，5+5是有进位的，此时，再加个尾指针，值为进位carry。
最后返回头指针head。
下面按代码进行了简单走一遍，方便理解。

方法二：添加初始值0

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode current = dummyHead;
        int carry = 0;

        while (l1 != null || l2 != null) {
            int x = (l1 != null) ? l1.val : 0;
            int y = (l2 != null) ? l2.val : 0;
            int sum = x + y + carry;
            carry = sum / 10; // 计算进位
            current.next = new ListNode(sum % 10);
            current = current.next;

            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }

        if (carry > 0) {
            current.next = new ListNode(carry);
        }
        return dummyHead.next;
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(2);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(3);

        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(4);

        Solution s = new Solution();
        ListNode result = s.addTwoNumbers(l1, l2);
        System.out.println(result.next.next.val);
        System.out.println(result.next.val);
        System.out.println(result.val);
    }
}
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