445. Add Two Numbers II

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up: What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

// Two Stacks + Iteration
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { // time: O(m + n); space: O(m + n)
    stack<int> s1, s2;
    // put every digits into s1 and s2
    while (l1) {
        s1.push(l1->val);
        l1 = l1->next;
    }
    while (l2) {
        s2.push(l2->val);
        l2 = l2->next;
    }
    int sum = 0;
    ListNode* res = new ListNode(0);
    while (!s1.empty() || !s2.empty()) {
        if (!s1.empty()) {
            sum += s1.top(); s1.pop();
        }
        if (!s2.empty()) {
            sum += s2.top(); s2.pop();
        }
        res->val = sum % 10;
        ListNode* head = new ListNode(sum / 10);
        head->next = res;
        res = head;
        sum /= 10;
    }
    if (res->val == 0) {
        ListNode* nodeToDelete = res;
        res = res->next;
        delete nodeToDelete;
    }
    return res;
}

// Recursion
int getLength(ListNode* head) {
    if (!head) return 0;
    int res = 0;
    while (head) {
        ++res;
        head = head->next;
    }
    return res;
}
ListNode* helper(ListNode* l1, ListNode* l2, int diff) {
    if (!l1) return nullptr;
    ListNode* res = diff == 0 ? new ListNode(l1->val + l2->val) : new ListNode(l1->val);
    ListNode* post = diff == 0 ? helper(l1->next, l2->next, 0) : helper(l1->next, l2, diff - 1);
    if (post && post->val > 9) {
        post->val %= 10;
        ++res->val;
    }
    res->next = post;
    return res;
}
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { // time: O(m + n); space: O(m + n)
    int m = getLength(l1), n = getLength(l2);
    ListNode* head = new ListNode(1);
    head->next = (m > n) ? helper(l1, l2, m - n) : helper(l2, l1, n - m);
    if (head->next->val > 9) {
        head->next->val %= 10;
    } else {
        ListNode* nodeToDelete = head;
        head = head->next;
        delete nodeToDelete;
    }
    return head;
}