题解 | 链表相加(二)“因为是单向链表所以：要逆置后再相加”

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */

    // 翻转链表：递归版！！！
    ListNode* reverse(ListNode* cur,ListNode* pre)
    {
        if(cur==nullptr) return pre;

        ListNode* tmp=cur->next;
        cur->next=pre;
        return reverse(tmp,cur);// 递归实际上就是，两个指针往前走的循环！
    }

     ListNode* ReverseList(ListNode* head)
     {
        if(head==nullptr||head->next==nullptr) return head;
        ListNode* cur=head;

        return reverse(cur,nullptr);
     }
    ListNode* addInList(ListNode* h1, ListNode* h2) 
    {
        if(h1==nullptr) return h2;
        if(h2==nullptr) return h1;// 0+任何数，都==它本身
        h1=ReverseList(h1);
        h2=ReverseList(h2);

        // 1、创建虚拟头结点
        ListNode* res=new ListNode(-1);
        ListNode* head=res;// head相当于cur，是结果链表的：移动指针

        // 2、设置进位
        int carry=0;

        // 3、只要链表没有遍历完+进位不为空，对逆置好了的链表，进行相加
        while(h1||h2||carry)
        {
            int val1= h1==nullptr?0:h1->val;
            int val2= h2==nullptr?0:h2->val;

            int x=carry+val1+val2;

            carry=x/10;
            int tmp=x%10;// tmp是相加后该位置的结果，就把tmp加入到new链表里面即可

            head->next=new ListNode(tmp);
            head=head->next;

            if(h1) h1=h1->next;
            if(h2) h2=h2->next;
        }

        return ReverseList(res->next);
    }
};