题解 | #两个链表生成相加链表#

class Solution {
public:
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        int len1=0,len2=0;
        head1=reverse(head1,len1);
        head2=reverse(head2,len2);
        ListNode* head;
        if(len1>=len2)
            head=head1;
        else
            head=head2;
        ListNode *p=head;
        int flag=0;//进位标志
        while(p){
            if(len1<len2&&head1)
                p->val+=head1->val;
            else if(len1>=len2&&head2)
                p->val+=head2->val;
            if(flag)
            {
                p->val+=1;
                flag=0;
            }
            if(p->val>9)
            {
                flag=1;
                p->val-=10;
            }
            if(len1>=len2&&head2)
                head2=head2->next;
            else if(len1<len2&&head1)
                head1=head1->next;
            if(!p->next)
            {
                if(flag)
                {
                    ListNode *tmp=(ListNode*)malloc(sizeof(ListNode));
                    tmp->val=1;
                    p->next=tmp;
                 }
            }
            p=p->next;
        }
        return reverse(head,len1);
    }
    ListNode * reverse(ListNode *head,int &length)
    {
        ListNode *p=head,*pre=NULL;
        while(p)
        {
            ListNode *tmp=p->next;
            p->next=pre;
            pre=p;
            p=tmp;
            length++;
        }
        return pre;
    }
};

反转链表，倒着相加，用flag表示进位