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

知识点：

本题考查的是单链表的基本操作。关于单链表，一些基本操作包括单链表的创建，添加，插入，删除。本题只用到了单链表的创建和添加。

首先是结构体的建立，这道题已经帮我们建立好了结构体，如下：

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

一个值，一个指向下一节点的指针，以及一个构造函数。重点注意：这个构造函数中的参数并未指定缺省值，所以我们在代码中不能出现这种语句：
<code> q = new ListNode;</code>
而必须要指定参数值，例如指定参数值为0，则代码应写为
<code> q = new ListNode(0);</code>
关于单链表的创建和添加，必须要有3个指针：头指针head用于指向单链表的开头，指针p指向单链表末尾，指针q用来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;
}

解题思路：

本题实际上就是大数加法。用一个变量carry表示进位，然后对应的位数相加的时候要加上进位，这个和记为oneSum。那么carry更新为oneSum / 10。除此之外，要考虑两个单链表长度不相等的情况。最后注意一下carry值是否有剩余。若有，则在结果最后添加上carry；若没有，则结束。
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;
    }
};