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

//三次反转列表即可
/**
 * 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* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        //将链表反转
        auto new_head1 = new ListNode(-1);
        ListNode *next;
        while(head1){
            next = head1->next;
            head1->next = new_head1->next;
            new_head1->next = head1;
            head1 = next;
        }
        head1 = new_head1->next;//链表1反转结束
        new_head1->next = nullptr;
        while(head2){
            next = head2->next;
            head2->next = new_head1->next;
            new_head1->next = head2;
            head2 = next;
        }
        head2 = new_head1->next;//链表2反转结束
        int carry = 0;
        auto left = head1,right = head2;
        ListNode *prev = nullptr;
        while(left && right){
            int res = left->val + right->val + carry;
            if(res >= 10){
                carry = 1;
                left->val = res - 10;
            }else{
                carry = 0;
                left->val = res;
            }
            prev = left;
            left = left->next;
            right = right->next;
        }
        while(left){
            int res = left->val + carry;
            if(res >= 10){
                carry = 1;
                left->val = res - 10;
            }else{
                carry = 0;
                left->val = res;
                break;
            }
            prev = left;
            left = left->next;
        }
        if(carry == 1)
            prev->next = new ListNode(1);
        if(right)prev->next = right;
        while(right){
            int res = right->val + carry;
            if(res >= 10){
                carry = 1;
                right->val = res - 10;
            }else{
                carry = 0;
                right->val = res;
                break;
            }
            prev = right;
            right = right->next;
        }
        if(carry == 1)
            prev->next = new ListNode(1);
        //再翻转下
        new_head1->next = nullptr;
        while(head1){
            next = head1->next;
            head1->next = new_head1->next;
            new_head1->next = head1;
            head1 = next;
        }
        return new_head1->next;
    }
};