题解 | #链表相加(二)#

struct ListNode*addlist(struct ListNode*a,struct ListNode*b,int cnt)//cnt进位
{
    if(a!=NULL&&b!=NULL){
        cnt+=a->val+b->val,a->val=cnt%10,a->next=addlist(a->next,b->next,cnt/10);
        return a;
    }
    if(a==NULL&&b==NULL&&cnt){
        struct ListNode*result=(struct ListNode*)malloc(sizeof(struct ListNode));
        result->val=cnt;
        result->next=NULL;
        return result;
    }
    if(a==NULL){
        if(!cnt)return b;
        cnt+=b->val,b->val=cnt%10,b->next=addlist(NULL,b->next,cnt/10);
        return b;
    }
    if(!cnt)return a;
    cnt+=a->val,a->val=cnt%10,a->next=addlist(a->next,NULL,cnt/10);
    return a;
}
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
    // write code here
    struct ListNode *o=(struct ListNode*)malloc(sizeof(struct ListNode)),*temp,*result;
    o->next=NULL;
    while(head1!=NULL)temp=head1,head1=head1->next,temp->next=o->next,o->next=temp;//倒转head1
    head1=o->next;
    o->next=NULL;
    while(head2!=NULL)temp=head2,head2=head2->next,temp->next=o->next,o->next=temp;//倒转head2
    head2=o->next;
    o->next=NULL;
    head1=addlist(head1,head2,0);//相加
    while(head1!=NULL)temp=head1,head1=head1->next,temp->next=o->next,o->next=temp;//将结果倒转
    result=o->next;
    return result;
}