1. question: 两数相加（中等）
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/add-two-numbers
示例 1：
1
2
3
| 输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
|
示例 2：
1
2
| 输入：l1 = [0], l2 = [0]
输出：[0]
|
示例 3：
1
2
| 输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
|
提示：
1
2
3
| 1. 每个链表中的节点数在范围 [1, 100] 内
2. 0 <= Node.val <= 9
3. 题目数据保证列表表示的数字不含前导零
|
2. answers
思路：
这道题比较直观，判断是否需要进位即可，另外在计算当前元素和的时候需要考虑上一位的进位，计算结果连接节点即可。
代码如下所示：
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
| class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val; this.next = next;
}
}
public class Solution_0002 {
public static ListNode addTwoNumbers(ListNode l1, ListNode l2){
ListNode head = new ListNode();
ListNode temp = head;
int next = 0;
while(l1 != null && l2 != null){
int result = l1.val + l2.val + next;
if(result > 9){
result = result % 10;
next = 1;
} else {
next = 0;
}
temp.next = new ListNode(result);
l1 = l1.next;
l2 = l2.next;
temp = temp.next;
}
while(l1 != null){
int result = l1.val + next;
if(result > 9){
result = result % 10;
next = 1;
} else {
next = 0;
}
temp.next = new ListNode(result);
l1 = l1.next;
temp = temp.next;
}
while(l2 != null){
int result = l2.val + next;
if(result > 9){
result = result % 10;
next = 1;
} else {
next = 0;
}
temp.next = new ListNode(result);
l2 = l2.next;
temp = temp.next;
}
if(next != 0){
temp.next = new ListNode(next);
}
return head.next;
}
public static void main(String[] args) {
ListNode l1 = new ListNode(0);
ListNode l2 = new ListNode(0);
ListNode result = addTwoNumbers(l1, l2);
while(result != null){
System.out.println(result.val);
result = result.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
| public static ListNode addTwoNumbers(ListNode l1, ListNode l2){
ListNode head = new ListNode();
ListNode temp = head;
int next = 0;
while(l1 != null || l2 != null){
int result = 0;
if(l1 == null){
result = l2.val + next;
} else if(l2 == null){
result = l1.val + next;
} else {
result = l1.val + l2.val + next;
}
if(result > 9){
result = result % 10;
next = 1;
} else {
next = 0;
}
temp.next = new ListNode(result);
if(l1 == null){
l2 = l2.next;
} else if(l2 == null){
l1 = l1.next;
} else{
l1 = l1.next;
l2 = l2.next;
}
temp = temp.next;
}
if(next != 0){
temp.next = new ListNode(next);
}
return head.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
| public static ListNode addTwoNumbers(ListNode l1, ListNode l2){
ListNode head = new ListNode();
ListNode temp = head;
int next = 0;
while(l1 != null || l2 != null){
int result = 0;
if(l1 == null){
result = l2.val + next;
} else if(l2 == null){
result = l1.val + next;
} else {
result = l1.val + l2.val + next;
}
if(result > 9){
result = result % 10;
next = 1;
} else {
next = 0;
}
if(l1 != null){
l1.val = result;
temp.next = l1;
} else {
l2.val = result;
temp.next = l2;
}
if(l1 == null){
l2 = l2.next;
} else if(l2 == null){
l1 = l1.next;
} else{
l1 = l1.next;
l2 = l2.next;
}
temp = temp.next;
}
if(next != 0){
temp.next = new ListNode(next);
}
return head.next;
}
|
最后，再次改进一下：判断非空的两部分修改如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
result += next;
if(l1 != null){
result += l1.val;
}
if(l2 != null){
result += l2.val;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
if(l1 != null){
l1 = l1.next;
}
if(l2 != null){
l2 = l2.next;
}
|
3. 备注
参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)。
