題目：
給出兩個(gè)?非空 的鏈表用來表示兩個(gè)非負(fù)的整數(shù)庐镐。其中，它們各自的位數(shù)是按照?逆序?的方式存儲的倾鲫，并且它們的每個(gè)節(jié)點(diǎn)只能存儲?一位?數(shù)字。
如果萍嬉，我們將這兩個(gè)數(shù)相加起來乌昔，則會返回一個(gè)新的鏈表來表示它們的和。
您可以假設(shè)除了數(shù)字 0 之外壤追，這兩個(gè)數(shù)都不會以 0?開頭磕道。
示例：
輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807
結(jié)題方法：初等數(shù)學(xué)
思路
我們使用變量來跟蹤進(jìn)位，并從包含最低有效位的表頭開始模擬逐位相加的過程行冰。
算法實(shí)現(xiàn)：
就像你在紙上計(jì)算兩個(gè)數(shù)字的和那樣溺蕉，我們首先從最低有效位也就是列表 l1l1 和 l2l2 的表頭開始相加。由于每位數(shù)字都應(yīng)當(dāng)處于 0 \ldots 90…9 的范圍內(nèi)悼做，我們計(jì)算兩個(gè)數(shù)字的和時(shí)可能會出現(xiàn) “溢出”疯特。例如，5 + 7 = 125+7=12肛走。在這種情況下漓雅，我們會將當(dāng)前位的數(shù)值設(shè)置為 22，并將進(jìn)位 carry = 1carry=1 帶入下一次迭代朽色。進(jìn)位 carrycarry 必定是 00 或 11邻吞，這是因?yàn)閮蓚€(gè)數(shù)字相加（考慮到進(jìn)位）可能出現(xiàn)的最大和為 9 + 9 + 1 = 199+9+1=19。
偽代碼如下：
將當(dāng)前結(jié)點(diǎn)初始化為返回列表的啞結(jié)點(diǎn)葫男。
將進(jìn)位 carrycarry 初始化為 00抱冷。
將 pp 和 qq 分別初始化為列表 l1l1 和 l2l2 的頭部。
遍歷列表 l1l1 和 l2l2 直至到達(dá)它們的尾端腾誉。
將 xx 設(shè)為結(jié)點(diǎn) pp 的值徘层。如果 pp 已經(jīng)到達(dá) l1l1 的末尾，則將其值設(shè)置為 00利职。
將 yy 設(shè)為結(jié)點(diǎn) qq 的值趣效。如果 qq 已經(jīng)到達(dá) l2l2 的末尾，則將其值設(shè)置為 00猪贪。
設(shè)定 sum = x + y + carrysum=x+y+carry跷敬。
更新進(jìn)位的值，carry = sum / 10carry=sum/10热押。
創(chuàng)建一個(gè)數(shù)值為 (sum \bmod 10)(summod10) 的新結(jié)點(diǎn)西傀，并將其設(shè)置為當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)斤寇，然后將當(dāng)前結(jié)點(diǎn)前進(jìn)到下一個(gè)結(jié)點(diǎn)。
同時(shí)拥褂，將 pp 和 qq 前進(jìn)到下一個(gè)結(jié)點(diǎn)娘锁。
檢查 carry = 1carry=1 是否成立，如果成立饺鹃，則向返回列表追加一個(gè)含有數(shù)字 11 的新結(jié)點(diǎn)莫秆。
返回啞結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)。
請注意悔详，我們使用啞結(jié)點(diǎn)來簡化代碼镊屎。如果沒有啞結(jié)點(diǎn)，則必須編寫額外的條件語句來初始化表頭的值茄螃。
官方解答：
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
? ? ListNode dummyHead = new ListNode(0);
? ? ListNode p = l1, q = l2, curr = dummyHead;
? ? int carry = 0;
? ? 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 dummyHead.next;
}
個(gè)人題解：
/**
* Definition for singly-linked list.
* public class ListNode {
*? ? int val;
*? ? ListNode next;
*? ? ListNode(int x) { val = x; }
* }
*/
class Solution {
? ? public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
? ? ? ? ListNode p = l1;
? ? ? ? ListNode q = l2;
? ? ? ? int addNum = 0;
? ? ? ? while(q!=null){
? ? ? ? ? ? if(p.next==null && q.next!=null)
? ? ? ? ? ? ? ? p.next = new ListNode(0);
? ? ? ? ? ? if(q.next==null && p.next!=null)
? ? ? ? ? ? ? ? q.next = new ListNode(0);
? ? ? ? ? ? int sumAll = addNum + p.val + q.val;
? ? ? ? ? ? p.val = sumAll % 10;
? ? ? ? ? ? addNum = sumAll / 10;
? ? ? ? ? ? if(p.next == null && q.next == null && addNum!=0)
? ? ? ? ? ? ? ? p.next = new ListNode(addNum);
? ? ? ? ? ? p = p.next;
? ? ? ? ? ? q = q.next;
? ? ? ? }
? ? ? ? return l1;
? ? }
}
轉(zhuǎn)載自：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/add-two-numbers/solution/liang-shu-xiang-jia-by-leetcode/
