题解 | #两个链表生成相加链表#

思路与两个字符串大数相加是一样的，只不过链表无法直接从后向前遍历，那么先将链表反转，然后从前向后遍历相加，设置进位，遍历完成后再将结果链表反转。注意使用dummy_node。

/**
 * 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* reverse_list(ListNode* head){
        ListNode* pre=nullptr;
        ListNode* cur=head;
        while(cur!=nullptr){
            auto temp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=temp;
        }
        return pre;
    }
    
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        ListNode* dummy_head=new ListNode{-1};
        ListNode* cur=dummy_head;
        ListNode* p1=reverse_list(head1);
        ListNode* p2=reverse_list(head2);
        int carry=0;
        while(p1!=nullptr || p2!=nullptr){
            int a{},b{};
            if(p1==nullptr) a=0;
            else a=p1->val;
            if(p2==nullptr) b=0;
            else b=p2->val;
            int sum=a+b+carry;
            ListNode* new_node=new ListNode{sum%10};
            cur->next=new_node;
            cur=cur->next;
            carry=sum/10;
            if(p1==nullptr) p1=nullptr;
            else p1=p1->next;
            if(p2==nullptr) p2=nullptr;
            else p2=p2->next;
        }
        auto result=reverse_list(dummy_head->next);
        return result;
    }
};