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 = [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.

/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) { val = x; }
* }
*/
public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
var res = Calculate(l1,l2);
return res;
}
private ListNode Calculate(ListNode l1, ListNode l2)
{
int carry=0;
int sum = l1.val + l2.val + carry;
carry = sum / 10;
var rootNode = new ListNode(sum % 10);
rootNode.next = CalculateRecursively(l1.next, l2.next, carry);
return rootNode;
}
private ListNode CalculateRecursively(ListNode l1, ListNode l2, int carry)
{
if (l1 == null && l2 == null)
{
if(carry != 0)
{
return new ListNode(carry);
}
return null;
}
int sum = 0;
var currentNode = new ListNode(0);
if(l1 == null)
{
sum = 0 + l2.val + carry;
carry = sum / 10;
currentNode = new ListNode(sum % 10);
currentNode.next = CalculateRecursively(l1, l2.next, carry);
}
else if(l2 == null)
{
sum = l1.val + 0 + carry;
carry = sum / 10;
currentNode = new ListNode(sum % 10);
currentNode.next = CalculateRecursively(l1.next, l2, carry);
}
else
{
sum = l1.val + l2.val + carry;
carry = sum / 10;
currentNode = new ListNode(sum % 10);
currentNode.next = CalculateRecursively(l1.next, l2.next, carry);
}
return currentNode;
}

We can do this question using both Recursive as well as Iterative approaches.

In the Recursive approach, we will go deep into the recursion until we meet our base condition (i.e both list nodes should be null) and at the same time we will be calculating the node sum and passing the carry to subsequent recursive calls. While doing so, in the end we will get our desired result.

In the Iterative approach, we will be looping through both lists until both become null, and at the same time we will be keeping track of the sum and carry of nodes and keep on adding them in one temp linked list that will contain our result.

Time Complexity: O(max(m,n)) // where m and n are the length of linked list 1 and linked list 2.

Space Complexity: O(max(m,n)+1) // where m and n are the length of the linked list 1 and linked list 2, and space is for storing the result in a separate linked list.