两数相加

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

大致意思：给定两个非空的链表代表两个非负整数，数字在链表中以倒序存储（意思就是好比如存储整数342，在链表中是2->4->3），链表中的每个结点存储一个数字。计算两个数字的和并以链表的形式返回。

约定两个数字不包含头部0的数字，除了0他本身。

常规解法：首先依次遍历两个链表，找到最长的那个链表作为主链表，每次遍历链表中的元素进行相加结果覆盖住链表中的值，最后短的链表遍历完后检查进位情况看是否在主链表中添加新的结点。这种方法比较通俗易懂，但是时间复杂度特别高。

/**
 * 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 *head=retLongList(l1,l2);
        ListNode *one=head;
        ListNode *two=NULL;
        if(one==l1)
        {
            two=l2;
        }
        else
        {
            two=l1;
        }
        int zv=0;
        while(one!=NULL && two!=NULL)
        {
            zv=(one->val+two->val)/10;
            one->val+=two->val;
            ListNode* fir=one;
            ListNode* sec=two;
            while(zv>0)
            {
                fir->val%=10;
                if(fir->next==NULL)
                {
                    fir->next=new ListNode(1);
                    fir->next->val=0;
                    fir->next->next=NULL;
                }
                fir->next->val+=zv;
                zv=fir->next->val/10;
                fir=fir->next;
            }
            one=one->next;
            two=two->next;
        }
        return head;
    }
    ListNode* retLongList(ListNode* l1, ListNode* l2)
    {
        ListNode* first=l1;
        ListNode* second=l2;
        while(1)
        {
            if(l1->next==NULL && l2->next==NULL)
            {
                return first;
            }
            else if(l1->next==NULL && l2->next!=NULL)
            {
                return second;
            }
            else if(l1->next!=NULL && l2->next==NULL)
            {
                return first;
            }
            else
            {
                l1=l1->next;
                l2=l2->next;
            }
        }
    }
};

其他解法：分别遍历两个链表，用一个变量表示是否有进位。某一个链表遍历完后，再将另一个链表没遍历完的连接在结果链表之后，如果最后有进位需要添加一个结点。时间复杂度较低。

class Solution {  
public:  
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {  
        int carry = 0;  
        ListNode* tail = new ListNode(0);  
        ListNode* ptr = tail;  
        while(l1 != NULL || l2 != NULL){  
            int val1 = 0;  
            if(l1 != NULL){  
                val1 = l1->val;  
                l1 = l1->next;  
            }    
            int val2 = 0;  
            if(l2 != NULL){  
                val2 = l2->val;  
                l2 = l2->next;  
            }       
            int tmp = val1 + val2 + carry;  
            ptr->next = new ListNode(tmp % 10);  
            carry = tmp / 10;  
            ptr = ptr->next;  
        }  
        if(carry == 1){  
            ptr->next = new ListNode(1);  
        }  
        return tail->next;  
    }  
};