需求：
給定兩個(gè)非空鏈表來(lái)表示兩個(gè)非負(fù)整數(shù)。位數(shù)按照逆序方式存儲(chǔ)挥唠，它們的每個(gè)節(jié)點(diǎn)只存儲(chǔ)單個(gè)數(shù)字抵恋。將兩數(shù)相加返回一個(gè)新的鏈表。
你可以假設(shè)除了數(shù)字 0 之外宝磨，這兩個(gè)數(shù)字都不會(huì)以零開(kāi)頭弧关。
示例：
輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807
分析：
1.將當(dāng)前結(jié)點(diǎn)初始化為返回列表的啞結(jié)點(diǎn)（要對(duì)頭結(jié)點(diǎn)進(jìn)行操作時(shí)盅安，考慮創(chuàng)建啞節(jié)點(diǎn)dummy，使用dummy->next表示真正的頭節(jié)點(diǎn)梯醒。這樣可以避免處理頭節(jié)點(diǎn)為空的邊界問(wèn)題）
2.將進(jìn)位 carry 初始化為 0宽堆。
3.將 p 和 q 分別初始化為列表 l1 和 l2 的頭部。
4.遍歷列表 l1 和 l2 直至到達(dá)它們的尾端茸习。
5.將 x 設(shè)為結(jié)點(diǎn) p 的值畜隶。如果 p 已經(jīng)到達(dá) l1的末尾，則將其值設(shè)置為 0号胚。
將 y 設(shè)為結(jié)點(diǎn) q 的值籽慢。如果 q 已經(jīng)到達(dá) l2 的末尾，則將其值設(shè)置為 0猫胁。
6.設(shè)定 sum = x + y + carry箱亿。更新進(jìn)位的值，carry = sum / 10弃秆。
7.創(chuàng)建一個(gè)數(shù)值為 (sum % 10)的新結(jié)點(diǎn)届惋，并將其設(shè)置為當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，然后將當(dāng)前結(jié)點(diǎn)前進(jìn)到下一個(gè)結(jié)點(diǎn)菠赚。
8.同時(shí)脑豹，將 p 和 q 前進(jìn)到下一個(gè)結(jié)點(diǎn)。檢查 carry = 1 是否成立衡查，如果成立瘩欺，則向返回列表追加一個(gè)含有數(shù)字 1 的新結(jié)點(diǎn)。返回啞結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)拌牲。
代碼：
/**
* 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) {
//定義啞結(jié)點(diǎn)
ListNode sumList = new ListNode(0);
ListNode p=l1, q=l2, curr = sumList;
int carry = 0;//進(jìn)位
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 sumList.next;
}
}
