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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

#include <stack>
class Solution {
public:
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        if (head1==nullptr) {
        return head2;
        }
        if (head2==nullptr) {
        return head1;
        }
        stack<int> st1,st2;    //利用堆栈将各自数字入栈，再pop相加
        ListNode *p1 = head1, *p2 = head2;
        while (p1!=nullptr) {
        st1.push(p1->val);
        p1=p1->next;
        }
        while (p2!=nullptr) {
        st2.push(p2->val);
        p2=p2->next;
        }
        int add=0; auto dump=new ListNode(-1);   //利用add标记是否进位
        dump->next=nullptr;
        while (!st1.empty()||!st2.empty()) {
            int v1=0,v2=0;
            if (!st1.empty()) {
            v1=st1.top();
            st1.pop();   
            }
            if (!st2.empty()) {
            v2=st2.top();
            st2.pop();   
            }
            int sum=v1+v2+add;
            add=0;
            if (sum>9) {
                sum=sum%10;
                add=1;
            }
            auto temp=new ListNode(sum); //将每次相加后的节点头插法插入新链表
            temp->next=dump->next;
            dump->next=temp;
        }
        if (add==1) {    //若最后为1代表最高位需要进位，则在头部插入进位节点1
        auto temp=new ListNode(add);
        temp->next=dump->next;
        dump->next=temp;
        }
        return dump->next;
    }
};