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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
        
    ListNode* ReverseList(ListNode* pHead, int* count) {
        if (!pHead){
            *count = 0;
            return pHead;
        }
        if (!pHead->next){
            *count = 1;
            return pHead;
        }
        ListNode* pFore = pHead;
        ListNode* p = pHead->next;
        pHead->next = nullptr;
        *count = 1;
        while(p){
            ListNode* pn = p->next;
            p ->next = pFore;
            pFore = p;
            p = pn;
            (*count) += 1;
        }
        
        return pFore;
    }

    ListNode* addInList(ListNode* head1, ListNode* head2) {
        int count1 = 0;
        int count2 = 0;
        ListNode* tail1 = ReverseList(head1, &count1);
        ListNode* tail2 = ReverseList(head2, &count2);

        int countDiff = count1 > count2 ? count1 - count2 : count2 - count1;

        if (countDiff > 0) {
            ListNode* shorter = count1 > count2 ? head2 : head1;
            while (countDiff > 0) {
                countDiff--;
                ListNode* temp = new ListNode(0);
                shorter->next = temp;
                shorter = temp;
            }
            if (count1 < count2){
                head1 = shorter;
            }
        }
        head1->next = new ListNode(0);
        head1 = head1->next;
        
        ListNode* pFore = nullptr;
        ListNode* p = tail1;
        
        while(tail2) {
            p->val += tail2->val;
            if (p->val > 9) {
                p->val %= 10;
                p->next->val += 1;
            }

            ListNode* pn = p->next;
            p -> next = pFore;
            pFore = p;
            p = pn;
            tail2 = tail2->next;
        }
        p -> next = pFore;
        if (head1->val == 0){
            head1 = head1->next;
        }
        return head1;
    }
};

1. 翻转
2. 补位
3. 边叠加边翻转