力扣热门100题——两数相加（推导，链表创建，进位问题）_力扣100

1、两数相加

1.问题描述

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

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

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

2.示例

示例 1：

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

输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：

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

3.提示

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

4.具体解法（链表创建，推导，进位问题）

//我的第一想法是创建第三个链表，遍历两个链表，都不为null就把val的和赋值给l3
//如果l1是null，那就把l2赋值给l3，反之一个道理
//然后三个链表都移动到下一个结点继续重复，知道l1和l2遍历完成都为null了
//但是在最后一步出现了问题，就是l3如何去指向下一个结点，他没有下一个结点
/*
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode l3=new ListNode();
        while(l1!=null||l2!=null){
            if(l1!=null&&l2!=null){
                l3.val=l1.val+l2.val;
            }
            else if(l1=null){
                l3.val=l2.val;
            }
            else if(l2=null){
                l3.val=l1.val;
            }
            l1=l1.next;
            l2=l2.next;
            l3=l3.next;//在这一步的代码其实是有问题的，l3是没有下一个结点的

        }
        return l3;
    }
}
 */
//所以就想到了用原来的l1或者l2去作为存储的容器
//可是谁做，显然应该是长的来做，那谁长谁短怎么判断
//想到了一个方法，就是我加到其中一个链表开始为空了，这个时候返回另一个就好了，那么前面存储的时候就应该两个串都存上和值
/*
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1==null){
            return l2;
        }
        else if(l2==null){
            return l1;
        }
        while(l1!=null||l2!=null){
            if(l1!=null&&l2!=null){
                l1.val=l1.val+l2.val;
                l2.val=l1.val;
            }
            else if(l1==null){
                return l2;
            }
            else {
                return l1;
            }
            l1=l1.next;
            l2=l2.next;

        }
        return l1;//这个地方理论上不用写返回的，但是没办法，因为不写不行，所以随便写了个返回l1
    }
}
 */
//系统执行出来了，但是测试用例都没通过，我发现是因为我们返回需要返回的是以前的链表开头
//所以应该一开始存储一个哨兵结点，不然输出的时候，两个链表已经不是最一开始的头结点了
//而且注意到，val的和会有可能大于等于10，所以得%10再赋值
/*
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode l3=l1;//存储l1一开始的位置，哨兵结点
        ListNode l4=l2;//存储l2一开始的位置
        if(l1==null){
            return l2;
        }
        else if(l2==null){
            return l1;
        }
        while(l1!=null||l2!=null){
            if(l1!=null&&l2!=null){
                l1.val=(l1.val+l2.val)%10;
                l2.val=l1.val;
            }
            else if(l1==null){
                return l4;
            }
            else {
                return l3;
            }
            l1=l1.next;
            l2=l2.next;

        }
        return null;//这个地方理论上不用写返回的，但是没办法，因为不写不行，所以随便写了个返回null
    }
}
 */
//输入
//[2,4,3]
//[5,6,4]
//输出：[]
//预期结果
//[7,0,8]
//不知道为什么懂的同学可以评论一下

//返回值还是一个空
//而且还发现另一个问题，就是测试用例三的情况，有进位的，我没有考虑进去
//如果上一个val的和大于10，除了%10保证这一位没问题，还应该设定一个标志位，标志位为true，我们应该加val+1

//放上一个大致思路相同的可以成功的代码
/*
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(-1), pre = dummyHead;
        int t = 0;
        while (l1 != null || l2 != null || t != 0) {
            if (l1 != null) {
                t += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                t += l2.val;
                l2 = l2.next;
            }
            pre.next = new ListNode(t % 10);
            pre = pre.next;
            t /= 10;
        }

        return dummyHead.next;
    }
}
 */
//附上一个更好理解的，跟我的思路几乎完全一样，并且解决了我的相关问题
/*
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //结果链表虚拟头结点
        ListNode dummyNode = new ListNode(-1);
        //结果链表工作指针
        ListNode cur = dummyNode;
        //定义进位
        int carry = 0;
        //模拟两数相加
        while(l1 != null || l2 != null){
            //本题难点：如果l1为空，l2不为空，则将l1的空对应值置为0，否则置为l1.val。l2亦然。
            //此处需要画图理解。
            int x = (l1 == null) ? 0 : l1.val;
            int y = (l2 == null) ? 0 : l2.val;
            //两数原始和（0-18）
            int sum = x + y + carry;
            //进位
            carry = sum / 10;
            //两数和（0-9）
            sum = sum % 10;
            //新建链表结点，将val赋值为sum
            cur.next = new ListNode(sum);//这句话非常关键，我之前不是说不知道怎么去给结果链表找下一个结点嘛，他这里就给了解决方法
                                         //将下一个结点创建出来并赋值就好了
            //指针后移到新结点上
            cur = cur.next;
            //两个工作指针后移
            if(l1 != null) l1 = l1.next;
            if(l2 != null) l2 = l2.next;
        }
        //难点：最后的进位是特殊情况，需要增加新结点并赋val值为1
        if(carry == 1){
            cur.next = new ListNode(1);
        }
        //返回结果链表的头结点
        return dummyNode.next;//而且这里返回的是.next，就不会返回第一个结点，那个结点存储的值是-1，真的是太妙了
    }
}
 */
//附上一个官方代码，都是大同小异，只有具体的细微差别
//说明我的解题思路完全是没问题的，但是具体的一些细节技术还没有把握好
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
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197

5.收获

• 学到一个新的说法：

  //结果链表虚拟头结点
  ListNode dummyNode = new ListNode(-1);
  1
  2

• 学习到了在链表处理中需要创建新的链表并跟随着遍历的时候，怎么去弄下一个结点的方法：

  cur.next = new ListNode(sum);
  //sum，可以是具体的参数
  //给一个参数是val，两个参数是val和next
  1
  2
  3

• 对于数字的处理也有了更多的熟练度，包括进位，获取个位，维持一个进位参数

• 唯一没想到的点，就是最后一个进位需要单独考虑的情况

• 是一道自己思路ok，但是操作还不ok的题目

• 小技巧：对于链表问题，返回结果为头结点时，通常需要先初始化一个预先指针 pre，该指针的下一个节点指向真正的头结点head。使用预先指针的目的在于链表初始化时无可用节点值，而且链表构造过程需要指针移动，进而会导致头指针丢失，无法返回结果。

  这个就是自己学到的新点，创建的链表头结点一般不真用，都是从next开始使用，并且要做好预先指针（哨兵结点）