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 {
current.next = add(l1, new ListNode(advance));
}
} else if (l2 != null) {
if (advance == 0) {
current.next = l2;
} else {
current.next = add(l2, new ListNode(advance));
}
}
// 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);
}
return head.next;
}
}
```

**Complexity Analysis**

- 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`

.

Categories: Linked List