两数相加

发表于
本文字数： 2.9k 阅读时长 ≈ 3 分钟

LeetCode每日一题，2. Add Two Numbers

先看题目描述

大意就是有两个用链表逆序存储的数字，让我们返回两数相加之和，和同样用链表逆序存储

算法和思路

思路就是模拟人计算的过程就可以，用 l1 来存储最终结果，把 l2 的值加到 l1 上，若 l1 的长度较短，则将 l2 多出来的部分接到链表 l1 后面，并注意对进位进行处理；若 l2 长度较短，则只需注意最后的对进位进行处理即可

算法源码

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode root = l1;
        int carry = 0;
        ListNode preNode1 = null;
        ListNode preNode2 = null;
        while (l1 != null && l2 != null) {
            l1.val = (l1.val + l2.val) % 10;
            carry = (l1.val + l2.val + carry) / 10;
            preNode1 = l1;
            preNode2 = l2;
            l1 = l1.next;
            l2 = l2.next;
        }
        if (l1 == null && l2 == null) {
            if (carry == 1) {
                preNode1.next = new ListNode(1);
            }
        } else if (l1 == null) {
            preNode1.next = l2;
            while (l2 != null && carry != 0) {
                l2.val = (l2.val + carry) % 10;
                carry = (l2.val + carry) / 10;
                preNode2 = l2;
                l2 = l2.next;
            }
            if (l2 == null && carry == 1) {
                preNode2.next = new ListNode(1);
            }
        } else {
            while (l1 != null && carry != 0) {
                l1.val = (l1.val + carry) % 10;
                carry = (l1.val + carry) / 10;
                preNode1 = l1;
                l1 = l1.next;
            }
            if (l1 == null && carry == 1) {
                preNode1.next = new ListNode(1);
            }
        }
        return root;
    }
}

题解同样是模拟人的计算，但采用了末尾补 0 的方式，效率差不多，但代码更加简洁

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