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

/**

 * 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* addInList(ListNode* head1, ListNode* head2) {

        // write code here

        if(!head1) return head2;

        if(!head2) return head1;

        /*head1 = reverse(head1);

        head2 = reverse(head2);

        ListNode* p1 = head1;

        ListNode* p2 = head2;

        ListNode* res = new ListNode(-1);

        ListNode* p3 = res;

        int m = 0;

        while(p1!=NULL||p2!=NULL){

            int val1 = p1==NULL ? 0:p1->val;

            int val2 = p2==NULL ? 0:p2->val;

            int sum =val1 + val2 +m;

            m = sum / 10;

            sum = sum % 10;

            ListNode* temp = new ListNode(sum);

            p3->next = temp;

            p3 = temp;

            if(p1!=NULL) p1 = p1->next;

            if(p2!=NULL) p2 = p2->next;

            cout<<temp->val<<" ";

        }

        if(m!=0){

            ListNode* temp = new ListNode(m);

            p3->next = temp;

        }

        res = reverse(res->next);

        return res;

    }

    ListNode* reverse(ListNode* head){

        if(!head) return NULL;

        ListNode* pre = nullptr;

        ListNode* nex;

        ListNode* cur = head;

        while(cur){

            nex = cur->next;

            cur->next = pre;

            pre = cur;

            cur = nex;

        }

        return pre;

    }

    */

    //栈方法

    stack<int> s1;

    stack<int> s2;

    stack<int> s3;

    ListNode* cur = head1;

    while(cur->next!=NULL){

        s1.push(cur->val);

        cur = cur->next;

    }

    s1.push(cur->val);

    cur->next = head2;

    cur = cur->next;

    while(cur!=NULL){

        s2.push(cur->val);

        cur = cur->next;

    }

    int m = 0;

    while(!s1.empty() || !s2.empty()){

        int val1;

        int val2;

        if(!s1.empty()){

            val1 = s1.top();

            s1.pop();

        }

        else{

            val1 = 0;

        }

        if(!s2.empty()){

            val2 = s2.top();

            s2.pop();

        }

        else{

            val2 = 0;

        }

        int sum = val1 + val2 + m;

        m = sum / 10;

        sum = sum % 10;

        s3.push(sum);

    }

    if(m!=0){

        s3.push(m);

    }

    ListNode* res = head1;

    while(!s3.empty()){

        head1->val = s3.top();

        s3.pop();

        if(s3.empty()) break;

        head1 = head1->next;

    }

    head1->next = nullptr;

    return res;

    }

};