[[286163]]

問：給出兩個非空的鏈表，來表示兩個非負的整數。其中，它們各自的位數是按照逆序的方式存儲的，并且每個結點只能存儲一位數字。將這兩個鏈表相加起來，返回一個新的鏈表，表示他們之和。

例如：342 + 465 = 807

兩數相加這道題，處理的就是最簡單的數學加法運算，只是它是建立在鏈表的基礎之上，所以難度在于對鏈表的處理。

加法運算，除了每一位的加法之外，還需要考慮進位的情況。針對這道題來說，鏈表的每一個結點存儲一位數字，并且是基于自然數字逆序存儲，也就是鏈頭到鏈尾保持低位到高位的順序，這樣就等于，進位的方向和單鏈表的方向一致。

由于單鏈表的特性，沒有前驅結點，無法回頭。在這道題的場景下，就只需要一次 while 循環，從鏈頭(低位)一直處理到鏈尾(高位)，就可以解決。但是需要注意處理進位的情況，每一位結點在計算之后，需要按 10 取余數，進行存儲，多的需要進位到下一結點參與運算，正好這也符合單鏈表的處理思路。

那么我們就需要幾個變量，一個 carry 用來記錄每一位運算后的進位，還需要一個 dummy 結點，用于記錄兩個鏈表加法運算后的鏈表結點。

當我們處理到最長鏈表最后一個結點時，還需要對 carry(進位) 進行額外的處理，如果 carry 不為 0，表示繼續向高位進位，需要額外在創建一個新的結點存儲進位。

到這里就講解清晰了，直接上代碼。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) { 
  // 計算結果存儲的 dummy 結點 
  ListNode dummy = new ListNode(0); 
  ListNode p = l1, q = l2, curr = dummy; 
  // 進位默認為 0 
  int carry = 0; 
  // 進入循環，以p和q兩個鏈表指針都走到頭為結束 
  while (p != null || q != null) { 
    int x = (p != null) ? p.val : 0; 
    int y = (q != null) ? q.val : 0; 
    // 進位參與運算 
    int sum = carry + x + y; 
    // 計算進位 
    carry = sum / 10; 
    // 構造新的結點存儲計算后的位數數值 
    curr.next = new ListNode(sum % 10); 
    curr = curr.next; 
    if (p != null)  
      p = p.next; 
    if (q != null)  
      q = q.next; 
  } 
  // 處理數字最高位末尾進位情況 
  if (carry > 0) { 
    curr.next = new ListNode(carry); 
  } 
  return dummy.next; 
} 

這里用 p 和 q 分別存儲了 l1 和 l2 兩個鏈表的結點，以此為循環依據。循環跳出的條件為兩個鏈表都走到了末尾。

每一次循環中，處理每一位結點數數值并加上進位 carry 的值，運算后將數值取余存入新的結點，并將新的進位數存入 carry 進行存儲。

最后需要注意，當兩個鏈表都處理完成之后，還需要判斷最高位是否需要進位(carry > 0)。如果需要，創建一個新的鏈表結點存儲進位值。

這道利用鏈表做加法運算的題，就講解到這里，但是它還有一些變種題。

假如鏈表不是逆序按位存儲數字呢?如果是正序存儲。

例如：

1 → 2 → 3

+ 3 → 2 → 1

=> 123 + 321 = ?

【本文為51CTO專欄作者“張旸”的原創稿件，轉載請通過微信公眾號聯系作者獲取授權】

戳這里，看該作者更多好文