# 02 Add Two Numbers

### Description

You are given two **non-empty** linked lists representing two non-negative integers. The digits are stored in **reverse order**, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

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

### Simple Solution

This problem is actually relatively simple as long as I am pretty familiar with linked list (not with c++ grammar however, which is necessary for me to catch up). Just set up one carrier bit, and then add up digits one by one. Sort like merging two sorted arrays.

### Code

```
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int carrier = 0;
ListNode* answer = new ListNode;
ListNode* ans = answer;
while (l1 != NULL && l2 != NULL) {
ans->val = (l1->val + l2->val + carrier) % 10;
carrier = (l1->val + l2->val + carrier) / 10;
if (l1->next != NULL || l2->next != NULL) {
ListNode* newNode = new ListNode;
ans = ans->next = newNode;
}
l1 = l1->next;
l2 = l2->next;
}
while (l1 != NULL) {
ans->val = (l1->val + carrier) % 10;
carrier = (l1->val + carrier) / 10;
if (l1->next != NULL) {
ListNode* newNode = new ListNode;
ans = ans->next = newNode;
}
l1 = l1->next;
}
while (l2 != NULL) {
ans->val = (l2->val + carrier) % 10;
carrier = (l2->val + carrier) / 10;
if (l2->next != NULL) {
ListNode* newNode = new ListNode;
ans = ans->next = newNode;
}
l2 = l2->next;
}
if (carrier != 0) {
ListNode* newNode = new ListNode;
ans = ans->next = newNode;
ans->val = carrier;
}
return answer;
}
};
```

### Complexity Analysis

Time complexity

This code need and only need one way look up. As a result, the time complexity is $O(n)$.

Space complexity

Only one linked list is need and one carrier int. So space complexity is also $O(n)$.