LeetCode刷題(2)——兩數相加

題目:

給出兩個 非空的連結串列用來表示兩個非負的整數。其中,它們各自的位數是按照 逆序 的方式儲存的,並且它們的每個節點只能儲存 一位 數字。如果,我們將這兩個數相加起來,則會返回一個新的連結串列來表示它們的和。您可以假設除了數字 0 之外,這兩個數都不會以 0 開頭

示例:

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

輸出:7 -> 0 -> 8

原因:342 + 465 = 807

方法一:遞迴實現

將方法理解為針對單個元素的相加,並將得到的新值作為結果輸出。Next部分有10進位制規則決定,縫10進1,若長度不等,則用0補齊,如下是演算法部分(C#):

LeetCode刷題(2)——兩數相加

方法二:非遞迴實現

們使用變數來跟蹤進位,並從包含最低有效位的表頭開始模擬逐位相加的過程。

LeetCode刷題(2)——兩數相加

將當前結點初始化為返回列表的啞結點。

將進位 carry 初始化為 0。

將 p 和 q 分別初始化為列表 l1 和 l2 的頭部。

遍歷列表 l1 和 l2 直至到達它們的尾端。

將 x 設為結點 p 的值。如果 p 已經到達 l1 的末尾,則將其值設定為 0。

將 y 設為結點 q 的值。如果 q 已經到達 l2 的末尾,則將其值設定為 0。

設定 sum = x + y + carry。

更新進位的值,carry = sum / 10。

建立一個數值為 (sum mod 10) 的新結點,並將其設定為當前結點的下一個結點,然後將當前結點前進到下一個結點。

同時,將 p 和 q 前進到下一個結點。

檢查 carry = 1是否成立,如果成立,則向返回列表追加一個含有數字 1 的新結點。

返回啞結點的下一個結點。

請注意,我們使用啞結點來簡化程式碼。如果沒有啞結點,則必須編寫額外的條件語句來初始化表頭的值。

LeetCode刷題(2)——兩數相加