题解 | 链表相加(二) (栈存储链表元素)

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <cstddef>
#include <stack>
using namespace std;

class Solution {
public:
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        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* dummy = new ListNode(0); // 创建哑节点作为结果链表头
        int carry = 0; // 进位值

        while (!a.empty() || !b.empty() || carry != 0) {
            int x = 0, y = 0;
            // 安全获取栈顶元素（栈空时为0）
            if (!a.empty()) {
                x = a.top();
                a.pop();
            }
            if (!b.empty()) {
                y = b.top();
                b.pop();
            }
            
            int sum = x + y + carry;
            carry = sum / 10;      // 计算进位
            int digit = sum % 10;  // 计算当前位值
            
            // 头插法创建新节点
            ListNode* newNode = new ListNode(digit);
            newNode->next = dummy->next;
            dummy->next = newNode;
        }
        
        return dummy->next;
    }
};