两个链表生成相加链表

题目链接：www.nowcoder.com/practice/c5…

思路加法肯定要从低位开始计算，刚开始想着把链表反转，这样链表首部就是低位了，但是这样也太麻烦了。可以用stack先把链表的数全存进去，再挨个拿出来，这样就可以从低位开始计算了

class Solution {
public:
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        if(head1 == nullptr) return head2;
        if(head2 == nullptr) return head1;

        //把数放入stack中
        stack<int> a,b;
        while(head1 != nullptr) {
            a.push(head1->val);
            head1 = head1->next;
        }
        while(head2 != nullptr) {
            b.push(head2->val);
            head2 = head2->next;
        }

        //头插法建造指针
        ListNode *now, *nex = nullptr;
        int flag = 0;
        while(!a.empty() || !b.empty()) {
            int x=0, y=0;
            if(!a.empty()) {
                x = a.top();
                a.pop();
            }
            if(!b.empty()) {
                y = b.top();
                b.pop();
            }
            now = new ListNode((x+y+flag)%10);
            flag = (x+y+flag)/10;

            now->next = nex;
            nex = now;
        }
        if(flag) {
            now = new ListNode(flag);
            now->next = nex;
        }
        return now;
    }
};
复制代码