You are given two linked lists representing two non-negative numbers. 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.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

注意：最后一位如果有进位，需要新创建一个结点来存放。

C++代码实现：

#include
     
      #include
      
       using namespace std;//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 *p=l1;        ListNode *pre=l1;        ListNode *q=l2;        int carry=0;        while(p&&q)        {            if(p->val+q->val+carry>9)            {                p->val=(p->val+q->val+carry)%10;                carry=1;            }            else            {                 p->val+=q->val+carry;                 carry=0;            }            pre=p;            p=p->next;            q=q->next;        }        if(q)            pre->next=q;        while(q)        {            if(q->val+carry>9)            {                q->val=(q->val+carry)%10;                carry=1;            }            else            {                q->val+=carry;                carry=0;                break;            }            pre=q;            q=q->next;        }        while(p)        {            if(p->val+carry>9)            {                p->val=(p->val+carry)%10;                carry=1;            }            else            {                p->val+=carry;                carry=0;                break;            }            pre=p;            p=p->next;        }        if(carry)        {            p=new ListNode(1);            pre->next=p;        }        return l1;    }    void createList(ListNode *&head,int *arr)    {        ListNode *p=NULL;        int i=0;        for(i=0; i<5; i++)        {            if(head==NULL)            {                head=new ListNode(arr[i]);                if(head==NULL)                    return;            }            else            {                p=new ListNode(arr[i]);                p->next=head;                head=p;            }        }    }};int main(){    Solution s;    ListNode *L1=NULL;    ListNode *L2=NULL;    ListNode *L=NULL;    int arr1[10]= {
   1,9,7,5,3};    int arr2[10]= {
   0,8,6,4,2};    s.createList(L1,arr1);    s.createList(L2,arr2);    L=s.addTwoNumbers(L1,L2);    while(L)    {        cout<
       
        val<<" ";        L=L->next;    }}
       
      
     

运行结果：

#include
     
      #include
      
       using namespace std;//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)    {        int carry=0;        ListNode *pre=l1;        ListNode *p=l1;        ListNode *q=l2;        while(p&&q)        {            p->val+=q->val+carry;            cout<
       
        val<
        
         val>9)            {                carry=1;                p->val=p->val%10;            }            else                carry=0;            pre=p;            p=p->next;            q=q->next;        }        if(q)        {            pre->next=q;            p=q;        }        while(p)        {            p->val=p->val+carry;            if(p->val>9)            {                p->val=p->val%10;                carry=1;            }            else            {                carry=0;                break;            }            pre=p;            p=p->next;        }        if(carry==1)            pre->next=new ListNode(1);        return l1;    }    void createList(ListNode *&L,int arr[],int n)    {        int i;        for(i=0; i
         
          next=L;                L=tmp;            }        }    }};int main(){    Solution s;    ListNode *L1=NULL;    ListNode *L2=NULL;    ListNode *L=NULL;    int arr1[10]= {8,9};    int arr2[10]= {1};    s.createList(L1,arr1,2);    s.createList(L2,arr2,1);    L=s.addTwoNumbers(L1,L2);    while(L)    {        cout<
          
           val<<" "; L=L->next; }}