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**