题解 | 链表相加(二)

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        stack<int> stk1, stk2;

        while (head1 || head2) {
            if (head1) {
                stk1.push(head1->val);
                head1 = head1->next;
            }
            if (head2) {
                stk2.push(head2->val);
                head2 = head2->next;
            }
        }

        int carry = 0;
        ListNode *head = nullptr;
        while (!stk1.empty() || !stk2.empty() || carry) {
            if (!stk1.empty()) {
                carry += stk1.top();
                stk1.pop();
            }
            if (!stk2.empty()) {
                carry += stk2.top();
                stk2.pop();
            }

            ListNode *node = new ListNode(carry % 10);
            node->next = head;
            head = node;
            carry /= 10;
        }
        return head;
    }
};