每天一道算法題-兩數相加

給你兩個非空的鏈表，表示兩個非負的整數。它們每位數字都是按照逆序的方式存儲的，并且每個節點只能存儲一位數字。

請你將兩個數相加，并以相同形式返回一個表示和的鏈表。

你可以假設除了數字 0 之外，這兩個數都不會以 0 開頭。

示例一：
輸入：l1 = [2,4,3], l2 = [5,6,4]
輸出：[7,0,8]
解釋：342 + 465 = 807.

示例二：
輸入：l1 = [0], l2 = [0]
輸出：[0]

示例三：
輸入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
輸出：[8,9,9,9,0,0,0,1]

首先，題目說兩個非空鏈表，每個節點存一位數字，而且是逆序存儲的。比如，數字342會被存為2->4->3這樣的鏈表。那我要把這樣的兩個鏈表相加，得到的結果同樣用逆序的鏈表表示。并且，除了數字0之外，這兩個數都不會以0開頭。那輸出的鏈表也應該符合這個條件，比如結果如果是0的話，就只能有一個節點。

那怎么做呢？我記得通常處理這種鏈表加法的時候，是模擬加法進位的過程。因為鏈表是逆序的，所以最低位在鏈表頭，這樣可以直接從頭開始相加，處理進位。這應該比較直接。

那步驟大概是這樣的：同時遍歷兩個鏈表，逐位相加，同時考慮進位。當其中一個鏈表遍歷完時，繼續處理剩下的節點，加上進位。最后如果還有進位，要新建一個節點。

比如例子中的情況：比如輸入是2->4->3（342）和5->6->4（465），相加得到807，結果應該是7->0->8。那鏈表就是7->0->8。這個過程需要處理每一位相加，進位保存下來加到下一位。

那具體實現的話，我需要創建兩個指針分別遍歷兩個鏈表，同時維護一個進位變量carry。每次取出兩個節點的值相加，加上carry，然后計算當前位的值（sum%10）和新的進位（sum/10）。然后將當前位的值作為新節點添加到結果鏈表中。直到兩個鏈表都遍歷完，并且進位為0為止。

這里需要注意的情況是，當兩個鏈表長度不一致的時候，較長的那個鏈表剩下的部分需要繼續處理。比如一個鏈表已經遍歷完，另一個還有節點，或者進位還存在的情況下要繼續處理。

舉個例子，比如鏈表1是9->9，鏈表2是9。那相加的話，結果應該是8->0->1。即99+9=108，逆序的話是8->0->1。這時候，當鏈表2遍歷完后，鏈表1還有節點，這時候要繼續處理剩下的節點，加上進位。

那如何實現呢？可以用循環，當鏈表1或鏈表2還有節點，或者進位不為零的時候繼續循環。在循環中，每次取出當前節點的值，如果鏈表已經到頭了，就取0。然后計算和，然后移動指針，如果鏈表還有下一個節點的話。

那現在考慮鏈表的遍歷方式。比如，用while循環，條件是l1不為空或者l2不為空或者carry不為零。這樣就能覆蓋所有情況。

比如，初始化進位carry為0。然后，在每次循環中：

? 取l1的當前值，如果l1不為空，否則取0。
? 取l2的當前值，如果l2不為空，否則取0。
? 計算sum = val1 + val2 + carry。
? 計算新的carry = sum / 10。
? 創建新節點，值為sum %10。
? 將新節點連接到結果鏈表的末尾。
? 移動l1和l2的指針（如果存在的話）。

但是，這樣處理的話，結果鏈表的構建需要維護一個當前指針，或者使用啞結點（dummy node）來簡化操作。啞結點的下一個節點是真正的頭節點，這樣可以避免處理初始空鏈表的情況。

比如，初始化一個dummy節點，然后維護一個當前指針curr，初始指向dummy。每次生成新節點時，curr.next指向它，然后curr移動到下一個節點。這樣最后返回dummy.next即可。

這樣就能處理所有情況，包括最后的進位。例如，當所有節點都處理完了，但還有進位1，這時候需要新建一個節點。

那現在編寫具體的代碼步驟：

創建一個啞結點dummy，curr指向dummy。
初始化carry為0。
當l1不為空，或l2不為空，或者carry不為0時循環：
a. 獲取l1的值，如果l1存在，否則為0。
b. 獲取l2的值，如果l2存在，否則為0。
c. 計算sum = val1 + val2 + carry。
d. 計算新的carry = sum /10。
e. 創建新節點，值為sum %10。
f. curr.next指向新節點，curr移動到next。
g. 如果l1不為空，l1移動到l1.next。
h. 如果l2不為空，l2移動到l2.next。
返回dummy.next作為結果鏈表的頭節點。

那這樣的邏輯應該可以覆蓋所有情況。

比如測試案例：

例子1：
輸入：l1 = [2,4,3], l2 = [5,6,4]
相加結果：342 + 465 = 807 → 逆序是7->0->8。
按照步驟：
初始化carry為0。
第一次循環：
val1=2，val2=5，sum=7+0=7。carry=0，新節點7。curr指向它。l1和l2都移動到下一個。
第二次循環：
val1=4，val2=6，sum=10+0=10。sum%10=0，carry=1。新節點0。curr指向它。l1和l2移動到下一位。
第三次循環：
val1=3，val2=4，sum=3+4+1=8 → sum%10=8，carry=0。新節點8。此時l1和l2都到頭了，但循環繼續嗎？因為此時carry為0，但是此時循環的條件是l1或l2不為空或carry不為零。此時l1和l2都是空，carry為0，所以退出循環。
結果鏈表是7->0->8。正確。

另一個例子，其中一個鏈表較長：
比如l1是9->9->9，l2是9->9。即數字是999和99，相加是1098。逆序存儲的話，鏈表應該是8->9->0->1。
處理過程：
初始carry=0。
第一次循環：9+9=18+0=18 → sum%10=8，carry=1。新節點8。l1和l2都移動。
第二次循環：9+9+1=19 → sum%10=9，carry=1。l1移動，l2為空。
第三次循環：9+0+1=10 → sum%10=0，carry=1。此時l1還有嗎？l1此時是第三個節點，處理完這次后，l1變為null。l2還是null，但carry是1。所以循環繼續。
第四次循環：0+0+1=1 → sum%10=1，carry=0。創建節點1。此時所有條件都不滿足，退出循環。結果鏈表是8->9->0->1。正確。

那這樣處理是正確的。

那關于啞結點的使用，這樣可以避免處理初始頭節點為空的情況，簡化代碼。

現在考慮代碼的實現，比如用Java的話：

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int val1 = (l1 != null) ? l1.val : 0;
int val2 = (l2 != null) ? l2.val : 0;
int sum = val1 + val2 + carry;
carry = sum / 10;
curr.next = new ListNode(sum % 10);
curr = curr.next;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
return dummy.next;
}

這樣應該可以正確處理所有情況。例如，當兩個鏈表都處理完，但還有進位的情況，比如最后進位為1時，會生成一個新節點。

那這個解法的時間復雜度是O(max(m, n))，其中m和n是兩個鏈表的長度，因為需要遍歷兩個鏈表的全部節點。空間復雜度是O(max(m, n))，因為需要創建結果鏈表，其長度最多為max(m,n)+1（比如最后進位的情況）。

那有沒有特殊情況需要處理？比如兩個鏈表都為空，但題目規定是非空的，所以不需要考慮。或者結果鏈表的前導零？題目說明除了數字0外，不會以0開頭，所以比如結果為0的情況只能是0本身，也就是一個節點。這種情況會在循環中處理嗎？

比如，輸入是兩個0的鏈表。則相加得到0，此時循環的條件是l1或l2不為空或carry不為零。初始時，l1和l2都是非空，所以進入循環：

val1=0，val2=0，sum=0+0+0=0，carry=0。創建節點0。然后l1和l2都移動到null。此時循環是否繼續？此時，l1和l2都為空，carry為0，所以不進入循環。返回dummy.next是節點0。正確。

那沒有問題。

另一個測試案例，比如l1是[9,9]，l2是[9]。相加得到18 + 9 = 99+9=108？或者原題中的例子是否應該更仔細？

比如，鏈表1是9->9，即99，逆序的話是99。鏈表2是9，即9。相加得到99+9=108。逆序存儲的話應該是8->0->1。按照上述代碼的處理：

第一次循環，sum是9+9+0=18 → sum%10=8，carry=1。節點8。l1移動，l2移動（到null）。
第二次循環，l1有節點9，val1=9，val2=0，sum=9+0+1=10 → sum%10=0，carry=1。節點0。l1移動（null）。
第三次循環，l1和l2都null，carry=1。sum=0+0+1=1 → sum%10=1，carry=0。節點1。此時循環結束。結果鏈表是8->0->1，正確。

綜上，這個代碼應該可以正確處理所有情況。

要將兩個逆序鏈表表示的數字相加并返回同樣格式的鏈表，可以按照以下步驟進行：

方法思路

初始化：使用啞結點（dummy node）簡化鏈表操作，并維護一個當前指針 curr 來構建結果鏈表。同時，用變量 carry 記錄進位值。
遍歷鏈表：同時遍歷兩個鏈表，逐位相加：
? 如果某個鏈表已遍歷完，則其后續位的值視為0。
? 計算當前位的和（包括進位），更新進位。
? 將當前位的值作為新節點添加到結果鏈表中。
處理剩余進位：若遍歷結束后仍有進位，需添加新節點。

解決代碼

class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) { this.val = val; }ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode dummy = new ListNode(0);ListNode curr = dummy;int carry = 0;while (l1 != null || l2 != null || carry != 0) {int val1 = (l1 != null) ? l1.val : 0;int val2 = (l2 != null) ? l2.val : 0;int sum = val1 + val2 + carry;carry = sum / 10;curr.next = new ListNode(sum % 10);curr = curr.next;if (l1 != null) l1 = l1.next;if (l2 != null) l2 = l2.next;}return dummy.next;}
}