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

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */

/*
大致思路：先翻转两链表，逐次相加，每次计算记录余数和进位，进位数作为下一次计算的依据；
当较短链表走到尽头时，将上次进位数纳入长链表剩余节点的计算。
当长链表也走到尽头时，判断最后一次加法运算是否产生进位：若有，则创造一个新节点写入；否则结束运算；得到翻转的链表和；再次翻转返回即可。
*/




#include <pthread.h>
class Solution {
  public:
    ListNode* reverseList(ListNode*& head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* p = head->next;
        ListNode* r = nullptr;

        head->next = nullptr;
        while (p) {
            r = p->next;
            p->next = head;
            head = p;
            p = r;
        }
        return head;
    }



    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        if (head1 == nullptr || head2 == nullptr) {
            return head1 == nullptr ? head2 : head1;
        }
        ListNode* a = reverseList(head1);
        ListNode* b = reverseList(head2);
        ListNode* virtual_head = new ListNode(-1);
        ListNode* pre = nullptr;
        virtual_head->next = a;
        int m = 0; //m表示相加所得余数
        int n = 0; //n表示相加所得进位
        while (a && b) {
             m = (a->val + b->val + n) % 10;
             n = (a->val + b->val + n) / 10;
            a->val = m;
            pre = a;
            a = a->next;
            b = b->next;
        }
        if (a == nullptr && b == nullptr) {
            //即两链表结点数一样时
            if (n) {
                ListNode* temp = new ListNode(0);
                temp->val = n;
                pre->next = temp;
            }


        } else {
            a = (a == nullptr ? b : a);
            pre->next = a;
            while (a) {
                m = ((a->val + n) % 10);
                n = ((a->val + n) / 10);
                a->val = m;
                pre = a;
                a = a->next;

            }
            if (n) {
                ListNode* temp1 = new ListNode(0);
                pre->next = temp1;
                temp1->val = n;
            }
        }


        return  reverseList(virtual_head->next);





    }
};