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.

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

Example 2:

```Input: l1 = , l2 = 
Output: 
```

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.

## Solution

Algorithm:

1. Create a dummy node result
.
2. Create two ListNode first and second and assign them l1 and l2.
3. Create two variable for maintaining divider and remainder and initialise with 0
4. While any of the ListNode not null, we will loop.
1. Calculate sum, remainder, divider for each iteration from two lists.
• sum = firstValue + secondValue + divider
• divider = sum / 10
• remainder = sum % 10
2. Assign remainder to next of response and shift response pointer to it’s next
3. Shift first and second to it’s next
5. If in the last divide has a value we we add it to next to response
6. Return result (dummy node)’s next.
```/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode result = new ListNode();
ListNode first = l1;
ListNode second = l2;
int divider = 0;
int remainder = 0;
ListNode response = result;
while(first!=null || second!=null){
int firstValue = (first!=null)?first.val:0;
int secondValue = (second!=null)?second.val:0;

int sum = firstValue + secondValue + divider;
divider = sum / 10;
remainder = sum % 10;
response.next = new ListNode(remainder);
response = response.next;
if(first!=null) first = first.next;
if(second!=null) second = second.next;
}

if(divider > 0){
response.next = new ListNode(divider);
}

return result.next;
}
}```

## Complexity :

### Time :

O(max(m,n)) – Assume that m and n represents the length of l1 and l2 respectively, the algorithm above iterates at most max(m, n) times.

### Space :

O(max(m,n)) –  O(max(m, n)) The length of the new list is at most max(m,n) + 1