# LeetCode Add Two Numbers

## Problem statement

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.

Problem statement taken from: https://leetcode.com/problems/add-two-numbers

**Example 1:**

```
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
```

**Example 2:**

```
Input: l1 = [0], l2 = [0]
Output: [0]
```

**Example 3:**

```
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
```

**Constraints:**

```
- The number of nodes in each linked list is in the range [1, 100].
- 0 <= Node.val <= 9
- It is guaranteed that the list represents a number that does not have leading zeros.
```

### Explanation

The numbers are represented in **reverse order** in LinkedList and hence
we do not have to worry about reversing the list.
The head of the LinkedList represent the least-significant digit
of the numbers.

Just like we add two numbers in Mathematics on a piece of paper,
we begin summing the least-significant digits.
As per the given constraint, each digit in the node is in the range
**0..9** so the sum may **overflow**.

For e.g., **4 + 9 = 13**. In this case, we set the current node digit to 3
and carry 1 to the next iteration.
The maximum sum can be **9 + 9 = 18**. So carry will be either 1 or 0.

##### Algorithm

```
- Initialize sum to 0.
- Initialize a current node which acts as a iterator and set the current sum as node val.
- Initialize pointer result which points to current node.
- Loop while(l1 != nil || l2 != nil)
- if ( l1 != nil )
- Add l1-> val to sum as sum += l1->val
- Move l1 to point next node l1 = l1->next
- if ( l2 != nil )
- Add l2-> val to sum as sum += l2->val
- Move l2 to point next node l2 = l2->next
- Initialize new ListNode with last digit of sum new ListNode( sum % 10 )
- Assign current node next to the new ListNode created above
- current->next = new ListNode( sum % 10 )
- Set current to current->next
- Set sum = sum / 10. sum / 10 will be 0 for sum < 10 and 1 for sum >= 10
- Check if sum > 9, if so append a new node with digit 1 to current node.
- Return result->next since result is still pointing to current's first position.
```

#### C++ solution

```
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int sum = 0;
ListNode result(0);
ListNode *current = &result;
while(l1 || l2){
if(l1){
sum += l1->val;
l1 = l1->next;
}
if(l2){
sum += l2->val;
l2 = l2->next;
}
current->next = new ListNode(sum % 10);
current = current->next;
sum = sum / 10;
}
if(sum > 0){
current->next = new ListNode(sum / 10);
}
return result.next;
}
};
```

#### Golang solution

```
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
sum := 0
current := new(ListNode)
result := current
for l1 != nil || l2 != nil {
if l1 != nil {
sum = sum + l1.Val
l1 = l1.Next
}
if l2 != nil {
sum = sum + l2.Val
l2 = l2.Next
}
current.Next = &ListNode{sum % 10, nil}
current = current.Next
sum = sum / 10
}
if sum > 0 {
current.Next = &ListNode{sum, nil}
}
return result.Next
}
```