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

//这道题需要从后面往前算，但是单链表不能逆向遍历，此时空间复杂度要求O(n),可以用栈存储起来，就可以逆向遍历了
//这里两个数相加最多是大的链表长度加1，为啥呢，假如两个两位数相加，最大也是小于两个最小的三位数相加，
//如 99+99 = 198(三位)，100+100=200(三位)，所以可以存储在长的链表中，然后看借进位是否大于0，大于零new一个节点存贮借进位，然后指向存储节点的头节点，这里注意长度相等的话，都得存储
#include <stack>
class Solution {
public:
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) 
    {
        int size1 = 0;
        int size2 = 0;
        stack<ListNode*> sta1;
        stack<ListNode*> sta2;
        ListNode* pNode1 = head1;
        ListNode* pNode2 = head2;
        while(pNode1||pNode2)
        {
            if(pNode1)
            {
                size1++;
                sta1.push(pNode1);
                pNode1 = pNode1->next;
            }
            if(pNode2)
            {
                size2++;
                sta2.push(pNode2);
                pNode2 = pNode2->next;
            }
        }
        ListNode *head = new ListNode(-1);
        head->next = nullptr;
        int c = 0;//借进位
        while(!sta1.empty()||!sta2.empty())
        {
            int a = 0;
            int b = 0;
            //a,b记录两个加数，若栈空，取0
            if(!sta1.empty()) a = sta1.top()->val;
            if(!sta2.empty()) b = sta2.top()->val;
            //相加之后存贮在链表长的链表中
            if(size1 > size2)  
            {
                sta1.top()->val = (a + b + c) % 10;
                c = (a + b + c) / 10;
            }
            else if(size1 < size2)
            {
                sta2.top()->val = (a + b + c) % 10;
                c = (a + b + c) / 10;
            }
            else 
            {
                 sta1.top()->val = (a + b + c) % 10;
                 sta2.top()->val = (a + b + c) % 10;
                 c = (a + b + c) / 10;
            }
            //不为空pop(),链表实际往前走
            if(!sta1.empty()) sta1.pop();
            if(!sta2.empty()) sta2.pop();
        }
        if(c>0)
        {
            head->val = c;
            head->next = size1>size2?head1:head2;
            return head;
        }
        else 
        {
            return size1>size2?head1:head2;
        }
    }
};