445.两数相加 II (Medium)*

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        // 用栈实现先遍历后计算
        stack<ListNode*> s1, s2;
        while(l1 != nullptr) {
            s1.push(l1);
            l1 = l1->next;
        }
        while(l2 != nullptr) {
            s2.push(l2);
            l2 = l2->next;
        }
        int flag = 0;
        stack<int> s3;
        while(!s1.empty() || !s2.empty() || flag == 1){
            int num = 0;
            if(!s1.empty()) {
                num += s1.top()->val;
                s1.pop();
            }
            if(!s2.empty()) {
                num += s2.top()->val;
                s2.pop();
            }
            num += flag;
            flag = num >= 10 ? 1 : 0;
            num = num%10;
            s3.push(num);
        }
        ListNode *head=new ListNode(s3.top());
        s3.pop();
        ListNode *p=head;
        while(!s3.empty()) {
            p->next = new ListNode(s3.top());
            s3.pop();
            p = p->next;       
        }
        return head;
    }
};