第二題：兩數(shù)相加
給出兩個(gè) 非空 的鏈表用來表示兩個(gè)非負(fù)的整數(shù)。其中，它們各自的位數(shù)是按照 逆序 的方式存儲的，并且它們的每個(gè)節(jié)點(diǎn)只能存儲 一位 數(shù)字。
如果，我們將這兩個(gè)數(shù)相加起來，則會返回一個(gè)新的鏈表來表示它們的和。
您可以假設(shè)除了數(shù)字 0 之外，這兩個(gè)數(shù)都不會以 0 開頭。
示例：
輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/check-permutation-lcci
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
V1版本
剛看到這個(gè)題目，就被誤導(dǎo)了，老套路，先暴力破解
解題思路
先提供兩個(gè)工具方法
1.鏈表轉(zhuǎn)整數(shù)
2.整數(shù)轉(zhuǎn)鏈表
執(zhí)行流程
1.將兩個(gè)鏈表轉(zhuǎn)成整數(shù)并相加
2.結(jié)得到的結(jié)果轉(zhuǎn)成鏈表
于是乎有了
鏈表轉(zhuǎn)int方法
例：鏈表 2 -> 4 -> 3 ==> 342
這個(gè)方法開始想復(fù)雜了，還想著先反轉(zhuǎn)鏈表后在計(jì)算整數(shù)值，寫完之后發(fā)現(xiàn)根本沒有畢要，
只需要循環(huán)鏈表，即 (2 * 10^0) + (4 * 10^1) + (3 * 10^2)，代碼如下
private static int convertToInt(ListNode list) {
// 結(jié)果整數(shù)
int result = 0;
// 索引位置
int index = 0;
while (list != null) {
// 整數(shù)累加
result += list.val * Math.pow(10, index++);
// 將下一個(gè)節(jié)點(diǎn)賦值給list，之前的節(jié)點(diǎn)由于沒有引用，后續(xù)會被垃圾回收器回收
list = list.next;
}
return result;
}
整數(shù)轉(zhuǎn)鏈表
例：整數(shù) 807 ==> 7 -> 0 -> 8
整數(shù)轉(zhuǎn)鏈表也很簡單，對整數(shù)依次 %10 和 /10，遍歷取出7、0、8,將數(shù)值放入鏈表返回即可，代碼如下
private ListNode convertToListNode(int num) {
// 第一個(gè)節(jié)點(diǎn)
ListNode result = new ListNode(num % 10);
// 將num
num /= 10;
// 定義臨時(shí)節(jié)點(diǎn)
ListNode node = result;
while (num > 0) {
node.next = new ListNode(num % 10);
num /= 10;
node = node.next;
}
return result;
}
只是讓我沒有想到的是，測試用例中的超長的鏈表，int根本不夠用，后改成long也不行，還有更長的鏈表
沒辦法，只能Plan B了
V2版本
一開始就說了被誤導(dǎo)了，其實(shí)認(rèn)真觀察可以發(fā)現(xiàn)，根本不需要轉(zhuǎn)來轉(zhuǎn)去
(2 -> 4 -> 3) + (5 -> 6 -> 4)
可以想成是
2 + 5 -> 4 + 6 -> 3 + 4
只是要注意兩條鏈表不對等及需要進(jìn)位的情況，代碼如下
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if (l1.val == 0) {
return l2;
}
if (l2.val == 0) {
return l1;
}
// 當(dāng)前節(jié)點(diǎn)的值
int num;
// 溢出值(進(jìn)位值),用于下一步累加，如6 + 6 = 12，那么 num = 2, overflowNum = 1
int overflowNum = 0;
// 兩個(gè)列表第一位進(jìn)行想加
num = l1.val + l2.val;
if (num >= 10) {
overflowNum = 1;
num %= 10;
}
// 返回的節(jié)點(diǎn)
ListNode resultNode = new ListNode(num);
// 兩個(gè)鏈表分別指向下一個(gè)鏈表
l1 = l1.next;
l2 = l2.next;
int val1, val2;
// 臨時(shí)節(jié)點(diǎn)
ListNode node = resultNode;
while (true) {
if (l1 == null && l2 == null) {
// 有進(jìn)位值則有一個(gè)節(jié)點(diǎn)
if (overflowNum == 1) {
node.next = new ListNode(1);
}
return resultNode;
}
val1 = l1 == null? 0 : l1.val;
val2 = l2 == null? 0 : l2.val;
// 這里需要將進(jìn)位值一起加上
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;
}
}
}
提交結(jié)果
為什么還會有0開頭的情況，是我誤解的
您可以假設(shè)除了數(shù)字 0 之外，這兩個(gè)數(shù)都不會以 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]
這種情況下，算完第一個(gè)數(shù)字之后，根本不需要在向下執(zhí)行下去，直接將后續(xù)長的鏈表接到結(jié)果鏈表返回就可以了，同步參考了評論區(qū)一個(gè)大佬的精簡代碼實(shí)現(xiàn)，代碼如下
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) {
// 當(dāng)l1不為空，l2已經(jīng)沒有了，且num也為0的情況下根本不需要繼續(xù)走下去了，下面同理
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;
}
// 將一個(gè)-1節(jié)點(diǎn)剔除
return resultNode.next;
}
后面還參考官版本寫了個(gè)V4，不過都大同小異，現(xiàn)在還是還是太慢了，一個(gè)這題目寫了5~6個(gè)小時(shí)，后續(xù)熟練后希望能提升點(diǎn)速度
