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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head1 ListNode类 
 * @param head2 ListNode类 
 * @return ListNode类
 */
struct ListNode* reverse(struct ListNode* head);
struct ListNode* createnode(int val){
    //为节点动态分配一块新的内存空间
    struct ListNode* newnode=(struct ListNode*)malloc(sizeof(struct ListNode));
    newnode->val=val;
    newnode->next=NULL;
    return newnode; 
}

struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
    // write code here
    if(head1==NULL) return head2;
    if(head2==NULL) return head1;
    //反转链表
    head1=reverse(head1);
    head2=reverse(head2);
    struct ListNode* head3=createnode(-1);
    struct ListNode* Hhead3=head3;
    
    //记录当前进位
    int tmp=0;
    while(head1!=NULL || head2!=NULL){
        //当前位相加之和（head1+head2+进位）
        int val=tmp;
        
        if(head1!=NULL){
            val+=head1->val;
            head1=head1->next;
        }
        if(head2!=NULL){
            val+=head2->val;
            head2=head2->next;
        }
        //生成新的进位
        tmp=val/10;
        //相加后当前位的节点
        Hhead3->next=createnode(val%10);
        Hhead3=Hhead3->next;
    }
    //当head1和head2均为空时，看tmp进位有没有数值
    if(tmp>0){
        Hhead3->next=createnode(tmp);
    }
    head3=head3->next;
    return reverse(head3);
}

struct ListNode* reverse(struct ListNode* head){
    if(head==NULL) 
        return head;
    struct ListNode* cur=head;
    struct ListNode* node=NULL;
    while(cur!=NULL){
        struct ListNode* tail=cur->next;
        cur->next=node;
        node=cur;
        cur=tail;
    }
    return node;
}