利用栈求解

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */

    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        stack<ListNode*> stack1;
        stack<ListNode*> stack2;
        stack<ListNode*> resultStack;
        ListNode* result = nullptr;
        ListNode* cur = nullptr;

        while (head1) {
            stack1.push(head1);
            head1 = head1->next;
        }
        while (head2) {
            stack2.push(head2);
            head2 = head2->next;
        }

        // 进位
        int tmp = 0;

        while (!stack1.empty() || !stack2.empty()) {
            int num1 = 0;
            int num2 = 0;

            if (!stack1.empty()) {
                num1 = stack1.top()->val;
                stack1.pop();
            }
            if (!stack2.empty()) {
                num2 = stack2.top()->val;
                stack2.pop();
            }

            int sumNum = num1 + num2 + tmp;
            ListNode* tmpNode = new ListNode(sumNum % 10);
            tmp = sumNum / 10;

            resultStack.push(tmpNode);
        }

        // 进位
        if (tmp > 0) {
            ListNode* tmpNode = new ListNode(tmp);
            tmpNode->next = nullptr;
            tmp = 0;
            resultStack.push(tmpNode);
        }

        while (!resultStack.empty()) {
            if (result) {
                cur->next = resultStack.top();
                cur = cur->next;
                resultStack.pop();
            }
            else {
                result = cur = resultStack.top();
                resultStack.pop();
            }
        }

        return result;
    }
};