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;
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);
}

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:

``````Node* temp = new Node(x);