/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    void myReverse(ListNode* &head)
    {
        if(head==NULL||head->next==NULL) return ;
        ListNode* pre=NULL,*p=head;
        while(p)
        {
            ListNode* t=p->next;
            p->next=pre;
            if(p) pre=p;
            p=t;
        }
        head=pre;
    }
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        //先将链表逆转
        myReverse(head1);
        myReverse(head2);
        //cout<<head2->val<<head2->next->val;
        //相加
        ListNode* p1=head1,*p2=head2;
        int num1,num2,carry=0;//carry  进位
        bool isfirst=1;
        ListNode* tail,*head;
        while(p1||p2)
        {
            if(p1)
            {
                num1=p1->val;
                p1=p1->next;
            }
            else num1=0;
            if(p2)
            {
                num2=p2->val;
                p2=p2->next;
            }
            else num2=0;
            ListNode* node=new ListNode(0);
            if(isfirst==1)
            {
                tail=node;
                head=node;
                tail->next=NULL;
                isfirst=0;
            }
            node->next=tail->next;
            if(tail!=node)
                tail->next=node;
            tail=node;
            node->val=(num1+num2+carry)%10;
            carry=(num1+num2+carry)/10;
            //cout<<carry<<endl;
        }
        if(carry) 
        {
            ListNode* node=new ListNode(carry);
            tail->next=node;
            node->next=NULL;
        }
        myReverse(head);
        return head;
    }
};