第二题：两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/check-permutation-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
V1版本
刚看到这个题目，就被误导了，老套路，先暴力破解
解题思路
先提供两个工具方法
1.链表转整数
2.整数转链表
执行流程
1.将两个链表转成整数并相加
2.结得到的结果转成链表
于是乎有了
链表转int方法
例：链表 2 -> 4 -> 3 ==> 342
这个方法开始想复杂了，还想着先反转链表后在计算整数值，写完之后发现根本没有毕要，
只需要循环链表，即 (2 * 10^0) + (4 * 10^1) + (3 * 10^2)，代码如下
private static int convertToInt(ListNode list) {
// 结果整数
int result = 0;
// 索引位置
int index = 0;
while (list != null) {
// 整数累加
result += list.val * Math.pow(10, index++);
// 将下一个节点赋值给list，之前的节点由于没有引用，后续会被垃圾回收器回收
list = list.next;
}
return result;
}
整数转链表
例：整数 807 ==> 7 -> 0 -> 8
整数转链表也很简单，对整数依次 %10 和 /10，遍历取出7、0、8,将数值放入链表返回即可，代码如下
private ListNode convertToListNode(int num) {
// 第一个节点
ListNode result = new ListNode(num % 10);
// 将num
num /= 10;
// 定义临时节点
ListNode node = result;
while (num > 0) {
node.next = new ListNode(num % 10);
num /= 10;
node = node.next;
}
return result;
}
只是让我没有想到的是，测试用例中的超长的链表，int根本不够用，后改成long也不行，还有更长的链表
没办法，只能Plan B了
V2版本
一开始就说了被误导了，其实认真观察可以发现，根本不需要转来转去
(2 -> 4 -> 3) + (5 -> 6 -> 4)
可以想成是
2 + 5 -> 4 + 6 -> 3 + 4
只是要注意两条链表不对等及需要进位的情况，代码如下
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if (l1.val == 0) {
return l2;
}
if (l2.val == 0) {
return l1;
}
// 当前节点的值
int num;
// 溢出值(进位值),用于下一步累加，如6 + 6 = 12，那么 num = 2, overflowNum = 1
int overflowNum = 0;
// 两个列表第一位进行想加
num = l1.val + l2.val;
if (num >= 10) {
overflowNum = 1;
num %= 10;
}
// 返回的节点
ListNode resultNode = new ListNode(num);
// 两个链表分别指向下一个链表
l1 = l1.next;
l2 = l2.next;
int val1, val2;
// 临时节点
ListNode node = resultNode;
while (true) {
if (l1 == null && l2 == null) {
// 有进位值则有一个节点
if (overflowNum == 1) {
node.next = new ListNode(1);
}
return resultNode;
}
val1 = l1 == null? 0 : l1.val;
val2 = l2 == null? 0 : l2.val;
// 这里需要将进位值一起加上
num = val1 + val2 + overflowNum;
if (num >= 10) {
overflowNum = 1;
num %= 10;
} else {
overflowNum = 0;
}
node.next = new ListNode(num);
node = node.next;
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
}
}
提交结果
为什么还会有0开头的情况，是我误解的
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
好吧，问题也不大，这里改一下就行了
if (l1.val == 0 && l1.next == null) {
return l2;
}
if (l2.val == 0 && l2.next == null) {
return l1;
}
V3版本
V3版本想解决的是
例：[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[1]
这种情况下，算完第一个数字之后，根本不需要在向下执行下去，直接将后续长的链表接到结果链表返回就可以了，同步参考了评论区一个大佬的精简代码实现，代码如下
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if (l1.val == 0 && l1.next == null) {
return l2;
}
if (l2.val == 0 && l2.next == null) {
return l1;
}
ListNode resultNode = new ListNode(-1);
ListNode node = resultNode;
int num = 0;
while (l1 != null || l2 != null || num != 0) {
// 当l1不为空，l2已经没有了，且num也为0的情况下根本不需要继续走下去了，下面同理
if (l1 != null && l2 == null && num == 0) {
node.next = l1;
return resultNode.next;
}
if (l1 == null && l2 != null && num == 0) {
node.next = l2;
return resultNode.next;
}
if (l1 != null) {
num += l1.val;
l1 = l1.next;
}
if (l2 != null) {
num += l2.val;
l2 = l2.next;
}
node.next = new ListNode(num % 10);
node = node.next;
num /= 10;
}
// 将一个-1节点剔除
return resultNode.next;
}
后面还参考官版本写了个V4，不过都大同小异，现在还是还是太慢了，一个这题目写了5~6个小时，后续熟练后希望能提升点速度
