2. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

知識(shí)點(diǎn)：

本題考查的是單鏈表的基本操作。關(guān)于單鏈表孟抗，一些基本操作包括單鏈表的創(chuàng)建，添加蹋凝，插入磅氨，刪除卤妒。本題只用到了單鏈表的創(chuàng)建和添加拢肆。

首先是結(jié)構(gòu)體的建立屋谭，這道題已經(jīng)幫我們建立好了結(jié)構(gòu)體辅斟，如下：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
 };

一個(gè)值转晰，一個(gè)指向下一節(jié)點(diǎn)的指針，以及一個(gè)構(gòu)造函數(shù)士飒。重點(diǎn)注意：這個(gè)構(gòu)造函數(shù)中的參數(shù)并未指定缺省值查邢，所以我們?cè)诖a中不能出現(xiàn)這種語(yǔ)句：
<code> q = new ListNode;</code>
而必須要指定參數(shù)值，例如指定參數(shù)值為0酵幕，則代碼應(yīng)寫(xiě)為
<code> q = new ListNode(0);</code>
關(guān)于單鏈表的創(chuàng)建和添加扰藕，必須要有3個(gè)指針：頭指針head用于指向單鏈表的開(kāi)頭，指針p指向單鏈表末尾芳撒，指針q用來(lái)new一塊空間邓深。添加操作就是用q指針new一塊空間，然后讓p指向q笔刹，最后p=p->next即可庐完，代碼如下：

ListNode *head, *p, *q;
head = new ListNode;
p = head;
//assume that the singly-linked list is 0->1->2
for (int i=0; i<3; ++i){
    q = new ListNode(i);
    p->next = q;
    p = p->next;
}

解題思路：

本題實(shí)際上就是大數(shù)加法。用一個(gè)變量carry表示進(jìn)位徘熔，然后對(duì)應(yīng)的位數(shù)相加的時(shí)候要加上進(jìn)位门躯，這個(gè)和記為oneSum。那么carry更新為oneSum / 10酷师。除此之外讶凉，要考慮兩個(gè)單鏈表長(zhǎng)度不相等的情況。最后注意一下carry值是否有剩余山孔。若有懂讯，則在結(jié)果最后添加上carry；若沒(méi)有台颠，則結(jié)束褐望。
C++代碼如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* rst = new ListNode(0);
        ListNode *p = rst, *q;
        int carry = 0, oneSum;
        while (l1 != NULL && l2 != NULL){
            oneSum = l1->val + l2->val + carry;
            q = new ListNode(oneSum % 10);
            p->next = q;
            p = p->next;
            carry = oneSum / 10;
            l1 = l1->next;
            l2 = l2->next;
        }
        //to find the remaining number
        ListNode* rmn;
        if (l1 == NULL && l2 == NULL)
            rmn = l1;
        else
            rmn = l1 != NULL? l1:l2;
        //to process the remaining number
        while (rmn != NULL){
            oneSum = rmn->val + carry;
            q = new ListNode(oneSum % 10);
            p->next = q;
            p = p->next;
            carry = oneSum / 10;
            rmn = rmn->next;
        }
        //to check whether carry is still non-zero
        if (carry != 0){
            q = new ListNode(carry);
            p->next = q;
            p = p->next;
        }
        return rst->next;
    }
};