LeetCode-2-两数相加

发表于 更新于 分类于 ，

LeetCode-2-两数相加

题目描述

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

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

示例:

1
2
3
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

我的思路

  1. 这个题的话,根据他们提供的ListNode类,按部就班的做下去就是可行的
  2. 首先逆序的数字相加,对于代码来说刚好是正序的,因为我们遍历链表时是从左往右的,刚好也是先对个位,十位,千位这样的顺序依次相加执行,所以和咱们平常的计算习惯并无太多差异
  3. 遍历链表时,个位与个位相加,十位与十位相加…(node1[0]与node2[0]相加,node1[1]与node2[1]相加....也`就是索引相同的部分相加)
  4. 如果两个node的当前索引都不为null,那就m=两数相加且要加上上次的进位计算,满10进1,所以当前索引保留m%10,进位m/10,若有其中一个为null,则另一个只用加进位即可
  5. 注意每次进入循环都要new 一个新的ListNode
  6. 因为在代码开头已经new 了ListNode ,所以最后取l3.next即为结果

我的代码

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
package com.dasnnj.practice.medium;

/**
 * Description <p> TODO:
 * 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
 * <p>
 * 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
 * <p>
 * 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 * <p>
 * 示例：
 * <p>
 * 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
 * 输出：7 -> 0 -> 8
 * 原因：342 + 465 = 807
 * </p>
 *
 * @author DASNNJ <a href="mailto:dasnnj@outlook.com"> dasnnj@outlook.com </a>
 * @date 2019-05-06 09:07
 */
public class TwoAdd {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode l3 = new ListNode(0);
        int m = 0;
        //进位
        int n = 0;
        ListNode l = l3;
        while (l1 != null || l2 != null) {
            l.next = new ListNode(0);
            l = l.next;
            if (l1 == null) {
                //则l2必然不为null
                //                l.val = l2.val + n;
                m = l2.val + n;
            } else if (l2 == null) {
                //则l1必然不为null
                //                l.val = l1.val + n;
                m = l1.val + n;
            } else {
                m = (l1.val + l2.val) + n;
            }
            n = m / 10;
            if (n > 0) {
                l.val = m % 10;
                //此步为了最后一个位置的两个数字加了之后需要进位
                l.next = new ListNode(n);
                //                l3.next.val = n;
            } else {
                l.val = m;
            }
            l1 = l1 == null ? null : l1.next;
            l2 = l2 == null ? null : l2.next;

        }
        return l3.next;

    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(8);
        l1.next.next = new ListNode(3);
        ListNode l2 = new ListNode(0);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(7);
        TwoAdd t = new TwoAdd();
        ListNode l3 = t.addTwoNumbers(l1, l2);
        System.out.println(l3);

    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) { val = x; }

    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder("ListNode{");
        sb.append("val=").append(val);
        sb.append(", next=").append(next);
        sb.append('}');
        return sb.toString();
    }
}