https://leetcode.com/problems/add-two-numbers-ii/

Different from LC 2, in this problem, the most significant digit comes first in the list. One easy solution is to reverse 2 lists and apply the algorithm in LC 2. The runtime O(n).

The follow up question requires us to not reverse the lists. We can tackle this by using recursion:

  • calculate the size of each list
  • add 0 to head of the shorter one to make 2 list's size equal.
  • add 2 list using recursion.
    ListNode* res;
    int carry = 0;
    
    int len(ListNode* u) {
        int count = 0;
        while (u) {
            count++;
            u = u->next;
        }
        return count;
    }
    
    ListNode* addZero(ListNode* u, int n) {
        for(int i = 1; i <= n; i++) {
            ListNode* temp = new ListNode(0);
            temp->next = u;
            u = temp;
        }
        return u;
    }
    
    void add(ListNode* u, ListNode* v) {
        if (!u) return;
        add(u->next, v->next);
        int sum = (u->val + v->val + carry) % 10;
        carry = (u->val + v->val + carry) / 10;
        ListNode* temp = new ListNode(sum);
        temp->next = res;
        res = temp;
    }
    
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int n = len(l1);
        int m = len(l2);
        
        if (n < m) {
            l1 = addZero(l1, m - n);
        } else if (n > m) {
            l2 = addZero(l2, n - m);
        }
        
        add(l1, l2);
        if (carry != 0) {
            ListNode* temp = new ListNode(carry);
            temp->next = res;
            res = temp;
        }
        
        return res;
    }

Runtime: O(n).

Two things can be learned from this simple problem:

  • add to the head of a list:
Node* temp = new Node(x);
temp->next = head;
head = temp;
  • when we need to do something bottom up, think about Recursion