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

/**
 * 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类
     */

    //转置这个链表
    void ReserveList(ListNode*& head)
    {
        if(head == nullptr) return ;
        ListNode* virhead = new ListNode(0);
        virhead->next = nullptr;
        ListNode* ss = head;
        ListNode* ssnext;
        while(ss!=nullptr)
        {
            ssnext = ss->next;
            ss->next = virhead->next;
            virhead->next = ss;
            ss = ssnext;
        }
        head = virhead->next;
        delete virhead;
    }

    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        ListNode* virhead = new ListNode(0);
        ListNode* p = head1;
        ListNode* q = head2;
        ReserveList(q);
        ReserveList(p);
        int sum = 0;
        while(p != nullptr && q != nullptr)
        {
            sum += p->val+q->val;
            ListNode* addNode = new ListNode(sum%10);
            addNode->next = virhead->next;
            virhead->next = addNode;
            sum /= 10;
            p = p->next;
            q = q->next;
        }

        while(p!=nullptr)
        {
            sum +=p->val;
            ListNode* addNode = new ListNode(sum%10);
            addNode->next = virhead->next;
            virhead->next = addNode;
            sum /= 10;
            p = p->next;
        }

        while(q!=nullptr)
        {
            sum += q->val;
            ListNode* addNode = new ListNode(sum%10);
            addNode->next = virhead->next;
            virhead->next = addNode;
            sum /= 10;
            q = q->next;
        }
        //判断还有没有进位，有就将头结点也当作值
        if(sum==0)
        {
            q = virhead->next;
            delete virhead;
        }
        else
        {
            virhead->val = sum;
            q = virhead;
        }
        return q;
    }
};