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

用原来的链表内存空间，省了一些内存。 思路就是如果一开始连接的短的链表，则最后将短链表尾部指向长链表长的一段

/**
 * 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类
     */
    ListNode *reverseList(ListNode *head){
        ListNode *pre=nullptr,*temp=head;
        while(head!=nullptr){
            temp=head->next;
            head->next=pre;
            pre=head;
            head=temp;
        }
        return pre;
    }
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        int flag=0;    //进位标识
        int num=0;
        ListNode *rh1=reverseList(head1);
        ListNode *rh2=reverseList(head2);
        ListNode *newhead=new ListNode(0);
        newhead->next=rh1;
        while(rh1->next!=nullptr && rh2->next!=nullptr){    //会剩下最后一个节点没作和
            num=rh1->val+flag+rh2->val;
            rh1->val=num%10;
            flag=num/10;
            rh1=rh1->next;
            rh2=rh2->next;
        }
        if(rh1->next==nullptr)
            rh1->next=rh2->next;        //若一开始将短的链表选作头，需要连接长的一段
        num=rh1->val+flag+rh2->val;
        rh1->val=num%10;
        flag=num/10;
        rh1=rh1->next;
        if(flag==0)
            return reverseList(newhead->next);
        while(rh1->next!=nullptr){        //留下最后一个结点
            num=rh1->val+flag;
            rh1->val=num%10;
            flag=num/10;
            rh1=rh1->next;
        }
        num=rh1->val+flag;                //处理最后的结点
        rh1->val=num%10;
        flag=num/10;
        if(flag>0){                        //结束后flag不为0，创建一个新的结点
            ListNode *p=new ListNode(flag);
            rh1->next=p;
        }
        return reverseList(newhead->next);
    }
};