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

先反转链表，在逐位相加

/**
 * 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(ListNode* head) {  // 反转链表
        ListNode* nex = nullptr;
        while (head != nullptr) {
            ListNode* tmp = head->next;
            head->next = nex;
            nex = head;
            head = tmp;
        }
        return nex;
    }

    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        ListNode* newHead1 = reverse(head1);  // 反转链表
        ListNode* newHead2 = reverse(head2);  // 反转链表
        ListNode *cur = new ListNode(0);
        int sum = 0;
        while(newHead1 && newHead2) {
            sum = newHead1->val + newHead2->val + cur->val;
            cur->val = sum/10;
            ListNode *ans = new ListNode(sum%10);
            ListNode *cn = cur->next;
            cur->next = ans;
            ans->next = cn;
            newHead1 = newHead1->next;
            newHead2 = newHead2->next;
        }
        while(newHead1) {
            sum = newHead1->val + cur->val;
            cur->val = sum/10;
            ListNode *ans = new ListNode(sum%10);
            ListNode *cn = cur->next;
            cur->next = ans;
            ans->next = cn;
            newHead1 = newHead1->next;
        }
        while(newHead2) {
            sum = newHead2->val + cur->val;
            cur->val = sum/10;
            ListNode *ans = new ListNode(sum%10);
            ListNode *cn = cur->next;
            cur->next = ans;
            ans->next = cn;
            newHead2 = newHead2->next;
        }
        return cur->val ? cur : cur->next;
    }
};