友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
445. 两数相加 II
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例1：
输入：l1 = [7,2,4,3], l2 = [5,6,4] 输出：[7,8,0,7]
示例2：
输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[8,0,7]
示例3：
输入：l1 = [0], l2 = [0] 输出：[0]
提示：
-
链表的长度范围为
[1, 100] -
0 <= node.val <= 9 -
输入数据保证链表代表的数字无前导 0
进阶：如果输入链表不能翻转该如何解决？
思路分析
最简单的办法是将链表翻转，求和再翻转回去。
将链表分为两种情况：
-
链表长度相等，则直接递归求和即可。
-
链表长度不等，则将链表以短链表的长度为准分割成收尾两部分
-
尾部直接相加
-
将尾部“嫁接”到首部
-
思路变化了三次：
-
最初的思路是使用 160. Intersection of Two Linked Lists 的思路，将链表长短拼接，这样两个链表就相等，相加后，再减去前面多余的节点。
-
后来的思路是“不全相加”，按照长链表的长度相加。
-
最后才想到将长链表分割的解法。
-
一刷
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-08-19 22:06:27
*/
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode len = null;
ListNode c1 = l1, c2 = l2;
while (c1 != null && c2 != null) {
c1 = c1.next;
c2 = c2.next;
if (c1 == null && c2 == null) {
break;
} else if (c1 == null) {
len = l2;
c1 = l2;
break;
} else if (c2 == null) {
len = l1;
c2 = l1;
break;
}
}
if (c1 == null && c2 == null) {
// 两个链表长度相等，则直接相加即可
ListNode result = add1(l1, l2);
return result.val == 0 ? result.next : result;
} else {
// 长度不等，则将链表以短链表的长度为准分割成收尾两部分
while (c1 != null && c1.next != null
&& c2 != null && c2.next != null) {
c1 = c1.next;
c2 = c2.next;
}
if (c1.next == null) {
c1 = l2;
ListNode tmp = c2.next;
c2.next = null;
c2 = tmp;
} else if (c2.next == null) {
c2 = l1;
ListNode tmp = c1.next;
c1.next = null;
c1 = tmp;
}
// 尾部直接相加
ListNode tail = add1(c1, c2);
// 将尾部“嫁接”到首部
ListNode result = add2(len, tail);
return result.val == 0 ? result.next : result;
}
}
private ListNode add2(ListNode len, ListNode tail) {
ListNode result;
if (len.next == null) {
result = tail;
} else {
result = add2(len.next, tail);
}
int sum = len.val + result.val;
ListNode head = new ListNode(sum / 10);
head.next = result;
result.val = sum % 10;
return head;
}
private ListNode add1(ListNode l1, ListNode l2) {
if ((l1 != null && l1.next == null)
&& (l2 != null && l2.next == null)) {
int sum = l1.val + l2.val;
ListNode head = new ListNode(sum / 10);
head.next = new ListNode(sum % 10);
return head;
}
ListNode result = add1(l1.next, l2.next);
int sum = l1.val + l2.val + result.val;
ListNode head = new ListNode(sum / 10);
head.next = result;
result.val = sum % 10;
return head;
}
参考资料
-
445. 两数相加 II - 简单Java — 借助栈来也是一个不错的解法。
-
445. 两数相加 II - 不用递归不用栈不翻转链表，原地计算 — 思路跟我类似，不过，他把短链表前面加了一些前导
0，这样一次递归相加即可。