首頁目錄 點擊查看
第一題
- 難度：中等
- 題目： 2. 兩數(shù)相加
給出兩個 非空 的鏈表用來表示兩個非負的整數(shù)吨枉。其中均芽，它們各自的位數(shù)是按照 逆序 的方式存儲的进泼，并且它們的每個節(jié)點只能存儲 一位 數(shù)字。
如果亡电，我們將這兩個數(shù)相加起來，則會返回一個新的鏈表來表示它們的和。
您可以假設(shè)除了數(shù)字 0 之外粥庄，這兩個數(shù)都不會以 0 開頭。
示例
輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807
解題思路
之前一直沒有碰過鏈表相關(guān)的東西豺妓，所以對于鏈表很陌生惜互，在JS前端環(huán)境也沒有鏈表這個東西，所以整體我都是參考題解來處理的琳拭。
我們使用變量來跟蹤進位训堆，并從包含最低有效位的表頭開始模擬逐位相加的過程。
image.png
圖1白嘁，對兩數(shù)相加方法的可視化: 342 + 465 = 807342+465=807坑鱼，每個結(jié)點都包含一個數(shù)字，并且數(shù)字按位逆序存儲絮缅。
就像你在紙上計算兩個數(shù)字的和那樣鲁沥，我們首先從最低有效位也就是列表 l1l1 和 l2l2 的表頭開始相加。由于每位數(shù)字都應(yīng)當處于 0 \ldots 90…9 的范圍內(nèi)耕魄，我們計算兩個數(shù)字的和時可能會出現(xiàn) “溢出”黍析。例如，5 + 7 = 125+7=12屎开。在這種情況下阐枣，我們會將當前位的數(shù)值設(shè)置為 22马靠，并將進位 carry = 1carry=1 帶入下一次迭代。進位 carrycarry 必定是 00 或 11蔼两，這是因為兩個數(shù)字相加（考慮到進位）可能出現(xiàn)的最大和為 9 + 9 + 1 = 199+9+1=19甩鳄。
偽代碼如下：
- 將當前結(jié)點初始化為返回列表的啞結(jié)點。
- 將進位 carrycarry 初始化為 00额划。
- 將 pp 和 qq 分別初始化為列表 l1l1 和 l2l2 的頭部妙啃。
- 遍歷列表 l1l1 和 l2l2 直至到達它們的尾端。
- 將 xx 設(shè)為結(jié)點 pp 的值俊戳。如果 pp 已經(jīng)到達 l1l1 的末尾揖赴，則將其值設(shè)置為 00。
- 將 yy 設(shè)為結(jié)點 qq 的值抑胎。如果 qq 已經(jīng)到達 l2l2 的末尾燥滑，則將其值設(shè)置為 00。
- 設(shè)定 sum = x + y + carrysum=x+y+carry阿逃。
- 更新進位的值铭拧，carry = sum / 10carry=sum/10。
- 創(chuàng)建一個數(shù)值為 (sum \bmod 10)(summod10) 的新結(jié)點恃锉，并將其設(shè)置為當前結(jié)點的下一個結(jié)點搀菩，然后將當前結(jié)點前進到下一個結(jié)點。
- 同時破托，將 pp 和 qq 前進到下一個結(jié)點肪跋。
- 檢查 carry = 1carry=1 是否成立，如果成立土砂，則向返回列表追加一個含有數(shù)字 11 的新結(jié)點州既。
- 返回啞結(jié)點的下一個結(jié)點。
請注意瘟芝，我們使用啞結(jié)點來簡化代碼易桃。如果沒有啞結(jié)點，則必須編寫額外的條件語句來初始化表頭的值锌俱。
請?zhí)貏e注意以下情況：
| 測試用例 | 說明 |
|---|---|
| l1=[0,1]l1=[0,1]晤郑，l2=[0,1,2]l2=[0,1,2] | 當一個列表比另一個列表長時 |
| l1=[]l1=[]戳晌，l2=[0,1]l2=[0,1] | 當一個列表為空時伦连，即出現(xiàn)空列表 |
| l1=[9,9]l1=[9,9]，l2=[1]l2=[1] | 求和運算最后可能出現(xiàn)額外的進位搅吁，這一點很容易被遺忘 |
答案
var addTwoNumbers = function (l1, l2) {
let node = new ListNode('head');
let temp = node;//啞結(jié)點
let add = 0;//是否進一
let sum = 0;//新鏈表當前未取余的值 = 鏈表1值 + 鏈表2值 + add;
//遍歷吭练，直到最長的都為空
while (l1 || l2) {
sum = (l1 ? l1.val : 0) + (l2 ? l2.val : 0) + add;
temp.next = new ListNode(sum % 10);//取余則為新鏈表的值
temp = temp.next;
add = sum >= 10 ? 1 : 0;
l1 && (l1 = l1.next);
l2 && (l2 = l2.next);
}
add && (temp.next = new ListNode(add))
return node.next;
};
image.png
第二題
- 難度：中等
- 題目：19. 刪除鏈表的倒數(shù)第N個節(jié)點
給定一個鏈表诫龙，刪除鏈表的倒數(shù)第 n 個節(jié)點，并且返回鏈表的頭結(jié)點鲫咽。
示例：
給定一個鏈表: 1->2->3->4->5, 和 n = 2.
當刪除了倒數(shù)第二個節(jié)點后签赃，鏈表變?yōu)?1->2->3->5.
解題思路
- 這道題還是鏈表題谷异，使用雙指針的思想確認要刪除的節(jié)點;n 是從 1 開始的(不是從 0 開始);
1 -> 2 -> 3 -> 4 -> 5 -> null
第一步: left與 right 的距離為 n + 1;
left right
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
第二步: 始終保持 left與 right 的距離為 n + 1, 向右移動, 直到 right 為 null, 此時 left 的位置就是要刪除節(jié)點上一個的位置。
left right
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
我的答案
var removeNthFromEnd = function (head, n) {
let summay = new ListNode(0);
summay.next = head;
let left = summay;
let right = summay;
let offset = n + 1
while (offset--) {
right = right.next;
if (offset > 1 && right === null) {
return summay.next
}
}
while (right) {
right = right.next;
left = left.next;
}
left.next = left.next.next
return summay.next
};
image.png
