LeetCode | Add Two Numbers II

https://leetcode.com/problems/add-two-numbers-ii/?tab=Description

思路：用两个数组（或者stack）存储链表每个节点的值，然后模拟大数加法。值得一提的是，最后没有必要将新构建的链表反转，因为链表可以在头部O(1)插入节点。

Time Complexity: O(n)

Space Complexity: O(n)

C++:

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        vector<int> vec1, vec2;
        while (l1) {
            vec1.push_back(l1->val);
            l1 = l1->next;
        }
        while (l2) {
            vec2.push_back(l2->val);
            l2 = l2->next;
        }
        int n1 = vec1.size(), n2 = vec2.size();
        int carry = 0, p1 = n1 - 1, p2 = n2 - 1;
        ListNode *head = new ListNode(0);
        while (true) {
            if (p1 >= 0) carry += vec1[p1--];
            if (p2 >= 0) carry += vec2[p2--];
            head->val = carry % 10; carry /= 10;
            if (p1 >= 0 || p2 >= 0 || carry != 0) {
                ListNode *new_head = new ListNode(0);
                new_head->next = head;
                head = new_head;
            } else break;
        }
        return head;
    }
};