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

/**
 * 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* pre = nullptr;
        ListNode* cur = head;
        while(cur){
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
    
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        /*
            1.加法法则是由低位到高位
            2.链表是由高位向低位表示数字
            3.两者逻辑相悖
            4.考虑翻转链表
            5.对每一位分别迭代操作
        */
        
        int quotient = 0;
        int remainder = 0;
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        head1 = reverse(head1);
        head2 = reverse(head2);
        
        while(head1 && head2){
            int sum = head1->val + head2->val + quotient;
            remainder = sum % 10;
            quotient = sum / 10;
            cur->next = new ListNode(remainder);
            cur = cur->next;
            head1 = head1->next;
            head2 = head2->next;
        }
        
        while(head1){
            int sum = head1->val + quotient;
            remainder = sum % 10;
            quotient = sum / 10;
            cur->next = new ListNode(remainder);
            cur = cur->next;
            head1 = head1->next;
        }
        
        while(head2){
            int sum = head2->val + quotient;
            remainder = sum % 10;
            quotient = sum / 10;
            cur->next = new ListNode(remainder);
            cur = cur->next;
            head2 = head2->next;
        }
        
        if(quotient){
            cur->next = new ListNode(quotient);
            cur = cur->next;
        }
        cur = reverse(dummy->next);
        return cur;
    }
};