# Add Two Numbers

Given two number represent by `LinkedList`calculate the sum of the numbers and store the result in a new LinkedList. Each node of the linked list is represented by single-digit and the head node is the most significant digit. For Example:

#### Example:

```Input:
First List: 3 → 6 → 5
Second List: 2 → 4 → 8

Output: (365 + 248) = 613
Resultant list: 6 → 1 → 3```

#### Intuition

First, we need to reverse both the linked list. Keep track of the `carry` using a variable and simulate digits-by-digits sum starting from the head of list, which contains the least-significant digit.

Visualization of the addition of two numbers:` (56712 + 6359 = 63,071).` Each node contains a single digit and the digits are stored in reverse order.

#### Algorithm:

• Create two `LinkedList` which will represent the above two numbers.
• Reverse both the linked list.
• Add two node values (Each node is being represented as single-digit)  starting from heads of two `LinkedList`.
• If the sum is of above two node values is more than 10, then forward the carry.
• Follow basic mathematical rules for addition.
• Once the addition is done then reverse the resultant `LinkedList` and return.

Just like how you would sum two numbers on a piece of paper, we begin by summing the least-significant digits, which is the head of `l1` and `l2`. Since each digit is in the range of 0…9, summing two digits may “overflow”.

For example `(5 + 7 =12)`. In this case, we set the current digit to 2 and bring over the `carry = 1` to the next iteration. Carry must be either 0 or 1 because the largest possible sum of two digits (including the carry) is `(9 + 9 + 1 = 19)`.

Following is the `LinkedList `ADT  `ListNode` we are going to use it to solve the problem.

```public class ListNode {
int val;
public ListNode next;

public ListNode(int x) {
val = x;
}
}```

Now traverse both lists. One by one pick nodes of both lists and add the values. If the sum is more than 10 then make `carry` as 1 and reduce `sum`. If one list has more elements than the other then consider remaining values of this list as 0. Following is the implementation of this approach.

```public class AddTwoNumbers {

public ListNode add(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode head = new ListNode(0);
ListNode current = head;
int advance = 0;
while (l1 != null && l2 != null) {
int sum = l1.val + l2.val + advance;
advance = sum / 10;
sum = sum % 10;
current.next = new ListNode(sum);
current = current.next;
l1 = l1.next;
l2 = l2.next;
}

if (l1 != null) {
if (advance == 0) {
current.next = l1;
} else {
}
} else if (l2 != null) {
if (advance == 0) {
current.next = l2;
} else {
}
}
// when both the lists are finished but still the carry
// is greater than 0. Example is (5+5) = 10
else if (l1 == null && l2 == null && advance > 0) {
current.next = new ListNode(advance);
}
• Time complexity : `O(max(m,n))`. Assume that `m` and `n` represent the length of `l1` and `l2` respectively, the algorithm above iterates at most `max(m,n)` times.
• Space complexity : `O(max(m,n))`. The length of the new list is at most `max(m,n)+1`.