Chatgpt v5.1 and v5.0 C++ 445. Add Two Numbers II

Here is one of the interview-favorite solutions: do the addition on-the-fly while you are popping the stacks that were built from the two lists.
No reversing the lists, no extra O(n) recursion, no dummy node; just two stacks and a carry.

```cpp
#include <stack>

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    explicit ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *n) : val(x), next(n) {}
};

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        std::stack<int> s1, s2;

        // push every digit into its own stack (MSB on top)
        for (; l1; l1 = l1->next) s1.push(l1->val);
        for (; l2; l2 = l2->next) s2.push(l2->val);

        ListNode *res = nullptr;   // head of the result list we are building
        int carry = 0;

        while (!s1.empty() || !s2.empty() || carry) {
            int a = s1.empty() ? 0 : s1.top(), b = s2.empty() ? 0 : s2.top();
            if (!s1.empty()) s1.pop();
            if (!s2.empty()) s2.pop();

            int sum = a + b + carry;
            carry = sum / 10;

            // prepend the new digit node
            auto *node = new ListNode(sum % 10);
            node->next = res;
            res = node;
        }
        return res;
    }
};
```

Complexities
- Time: O(n + m) – each node is pushed and popped once.
- Extra space: O(n + m) – the two stacks (you can shrink it to O(1) by reversing the lists in-place if you want).