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

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head1 ListNode类 
 * @param head2 ListNode类 
 * @return ListNode类
 */
#include <stdio.h>
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
    // write code here
    struct ListNode* cur;
    struct ListNode* pre;
    struct ListNode* temp;
    struct ListNode* cur1;
    struct ListNode* pre1;
    struct ListNode* temp1;
    struct ListNode* p=(struct ListNode*)malloc(sizeof(struct ListNode));
    p=NULL;
    int carrybit=0;
    if(head1==NULL||head2==NULL)
    return NULL;
    pre=NULL;
    pre1=NULL;
    cur=head1;
    cur1=head2;
    while(cur||cur1)//反转链表
    {
        if(cur!=NULL)
        {   
            temp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=temp;
        }
        if(cur1!=NULL)
        {
            temp1=cur1->next;
            cur1->next=pre1;
            pre1=cur1;
            cur1=temp1;
        }
    }
    struct ListNode* phead1=pre;
    struct ListNode* phead2=pre1;
    while(phead1!=NULL||phead2!=NULL||carrybit!=0)//最后可能进位
    {
        int t;
        t=(phead1==NULL?0:phead1->val)+(phead2==NULL?0:phead2->val)+carrybit;
        if(t>9)
        {
            carrybit=t/10;
            t%=10;
        }
        else {
        carrybit=0;
        }
        if(p==NULL)
        {
            struct ListNode *q=malloc(sizeof(struct ListNode));
            q->val=t;
            q->next=NULL;
            p=q;
        }
        else//头插法 
        {
        struct ListNode *k=malloc(sizeof(struct ListNode));
        k->val=t;
        k->next=p;
        p=k;
        }
        if(phead1!=NULL)
        phead1=phead1->next;
        if(phead2!=NULL)
        phead2=phead2->next;
    }
    return p;
}