[[286163]]

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

例如：342 + 465 = 807

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

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

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

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

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

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

public ListNode addTwoNumbers(ListNode l1, ListNode l2) { 
  // 計算結(jié)果存儲的 dummy 結(jié)點 
  ListNode dummy = new ListNode(0); 
  ListNode p = l1, q = l2, curr = dummy; 
  // 進位默認為 0 
  int carry = 0; 
  // 進入循環(huán)，以p和q兩個鏈表指針都走到頭為結(jié)束 
  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; 
    // 構(gòu)造新的結(jié)點存儲計算后的位數(shù)數(shù)值 
    curr.next = new ListNode(sum % 10); 
    curr = curr.next; 
    if (p != null)  
      p = p.next; 
    if (q != null)  
      q = q.next; 
  } 
  // 處理數(shù)字最高位末尾進位情況 
  if (carry > 0) { 
    curr.next = new ListNode(carry); 
  } 
  return dummy.next; 
} 

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

每一次循環(huán)中，處理每一位結(jié)點數(shù)數(shù)值并加上進位 carry 的值，運算后將數(shù)值取余存入新的結(jié)點，并將新的進位數(shù)存入 carry 進行存儲。

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

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

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

例如：

1 → 2 → 3

+ 3 → 2 → 1

=> 123 + 321 = ?

【本文為51CTO專欄作者“張旸”的原創(chuàng)稿件，轉(zhuǎn)載請通過微信公眾號聯(lián)系作者獲取授權(quán)】

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