算法連載之求解兩數相加 Add Two Numbers

求解兩數相加

兩個非空的鏈表用來表示兩個非負的整數。其中，它們各自的位數是按照逆序的方式存儲的，並且它們的每個節點只能存儲一位數字。

如果，將這兩個數相加起來，則會返回一個新的鏈表來表示它們的和。

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

示例：

輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)

輸出：7 -> 0 -> 8

原因：342 + 465 = 807

實現

同時遍歷l1和l2兩個鏈表，將兩個節點值相加作為返回鏈表的新節點。有兩種特殊情況：

1、其中一個鏈表已經全部遍歷完成，則只關注兩一個鏈表的節點作為加數即可，因為另一個鏈表已遍歷完成，所以可以看作加數為0。

2、兩個鏈表節點之和若存在進位的情況，則先記錄，下一次遍歷時同加數相加。如果兩個鏈表均遍歷完成，仍然有進位，則新建一個節點存儲進位。

若l1和l2兩個鏈表長度分別是n和m，時間複雜度是O(max(n,m))；由於新增返回鏈表，長度至少是兩個鏈表的最大長度，所以空間複雜度是O(max(n,m))。

拓展問題

各自的位數是按照正序的方式存儲。

示例：

輸入：(3 -> 4 -> 2) + (4 -> 6 -> 5)

輸出：8 -> 0 -> 7

原因：342 + 465 = 807

可以藉助棧的後進先出特性來解決。首先將兩個鏈表分別壓入兩個棧中，相加的主算法與逆序的方式相似。區別是：由於返回的鏈表也是正序的，低位運算的節點要作為後繼節點，始終向鏈表頭添加。

時間複雜度仍然是O(max(n,m))；新增返回鏈表和兩個輔助棧，空間複雜度是O(max(n,m))。