题解 | 链表相加(二)

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // 使用栈来反转链表顺序，便于从低位开始相加
        stack<int> stack1, stack2;

        // 将链表1的节点值压入栈中
        ListNode* p1 = head1;
        while (p1 != nullptr) {
            stack1.push(p1->val);
            p1 = p1->next;
        }

        // 将链表2的节点值压入栈中
        ListNode* p2 = head2;
        while (p2 != nullptr) {
            stack2.push(p2->val);
            p2 = p2->next;
        }

        int carry = 0;  // 进位
        ListNode* head = nullptr;  // 结果链表的头节点

        // 当两个栈不为空或还有进位时，继续计算
        while (!stack1.empty() || !stack2.empty() || carry != 0) {
            int val1 = 0, val2 = 0;

            // 从栈中取出当前位的值
            if (!stack1.empty()) {
                val1 = stack1.top();
                stack1.pop();
            }
            if (!stack2.empty()) {
                val2 = stack2.top();
                stack2.pop();
            }

            // 计算当前位的和及进位
            int total = val1 + val2 + carry;
            carry = total / 10;
            int digit = total % 10;

            // 使用头插法创建新节点，确保结果链表的顺序正确
            ListNode* new_node = new ListNode(digit);
            new_node->next = head;
            head = new_node;
        }

        return head;
    }
};