一祠汇、題目
給你兩個非空的鏈表吕晌，表示兩個非負的整數(shù)。它們每位數(shù)字都是按照 逆序 的方式存儲的遥金，并且每個節(jié)點只能存儲 一位 數(shù)字浴捆。
請你將兩個數(shù)相加，并以相同形式返回一個表示和的鏈表稿械。
你可以假設(shè)除了數(shù)字0之外选泻，這兩個數(shù)都不會以0開頭。
二、示例
示例 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]
提示：
- 每個鏈表中的節(jié)點數(shù)在范圍
[1, 100]內(nèi)0 <= Node.val <= 9- 題目數(shù)據(jù)保證列表表示的數(shù)字不含前導(dǎo)零
ListNode的結(jié)構(gòu)：
它是一個單向鏈表页眯，由next引用下一個節(jié)點梯捕。
三、解題思路
看完這道題窝撵，第一個想法就是科阎，按位進行相加操作，并將結(jié)果保存新的節(jié)點中忿族，即：new ListNode(l1.val + l2.val)。那么如果相加的總和大于9的話蝌矛，則需要執(zhí)行進位操作道批，我們這里使用int carryBit來保存進位值（默認為0，進位則被賦值為1）入撒。所以隆豹，新節(jié)點的創(chuàng)建其實應(yīng)該是new ListNode(l1.val + l2.val + carryBit)。如下圖所示：
這里面有一個小的優(yōu)化點茅逮，就是在于如果兩個鏈表長度不一樣璃赡，短鏈表遍歷完畢后，我們是如何處理長鏈表剩余未遍歷的部分的献雅。這里面有兩種情況碉考，如果carryBit等于1，即：需要進位挺身，那么就還是按照進位操作的方式計算并創(chuàng)建新的節(jié)點侯谁。但是，如果不需要進位章钾，即：carryBit等于0墙贱，那么我們其實可以直接將剩余部分的鏈表“拼接”到新的鏈表中。如下圖所示贱傀，我們只需要將Node(8).next=Node(2)即可惨撇，免去了遍歷的操作。
四府寒、代碼實現(xiàn)
class SolutionOf2 {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode headNode = null;
ListNode temp = null;
int carryBit = 0;
while (true) {
// 有一個或者兩個都是末尾節(jié)點,并且沒有進位魁衙，則跳出循環(huán)
if ((l1 == null || l2 == null) && carryBit == 0) {
temp.next = (l1 != null) ? l1 : l2;
break;
}
// 判斷兩個節(jié)點相加后，是否需要進位
int sum;
if ((sum = (l1 != null ? l1.val : 0) + (l2 != null ? l2.val : 0) + carryBit) > 9) {
sum -= 10;
carryBit = 1;
} else {
carryBit = 0;
}
ListNode sumNode = new ListNode(sum);
if (headNode == null) {
headNode = sumNode;
} else {
temp.next = sumNode;
}
temp = sumNode;
l1 = l1 != null ? l1.next : null;
l2 = l2 != null ? l2.next : null;
}
return headNode;
}
}
今天的文章內(nèi)容就這些了椰棘，最后一句話：
寫作不易纺棺，筆者幾個小時甚至數(shù)天完成的一篇文章，只愿換來您幾秒鐘的點贊&分享邪狞。
更多技術(shù)干貨祷蝌，歡迎大家關(guān)注公眾號“爪哇繆斯”(o)/~ 「干貨分享，每周更新」
題目來源：力扣
