## Add two numbers represented by Linked List

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

Example 1

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

Output:
Resultant list: 6 → 1 → 3```
```
Example 2```
```Input:
First List: 1 →  5 →  1 →  8
Second List: 3 →  6 →  9 →  8 →  7

Output
Resultant list:  →   →   →   →  ```
```
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 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.

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

Node.Java

```package algorithm.linkedlist;

public class Node<T> {

T data;
Node next;

public Node(T data) {
this.data = data;
this.next = null;
}

public void print() {
String printValue = "[ " + this.data + "] ";
if (next != null) {
printValue += "---> ";
}
System.out.print(printValue);
}
}
```

```package algorithm.linkedlist;

public class LinkedList {

public LinkedList(Node node) {
}

public void add(Node node) {
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = node;
}
}
```

Now traverse both lists. One by one pick nodes of both lists and add the values. If 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.

`TwoNumber.java`
```package algorithm.linkedlist;

public class TwoNumber {

if (head1 == null)
if (head2 == null)

Node head = new Node(0);
Node current = head;
int advance = 0;
while (head1 != null && head2 != null) {
advance = sum / 10;
sum = sum % 10;
current.next = new Node(sum);
current = current.next;
}

if (head1 != null) {
if (advance == 0) {
} else {
}
} else if (head2 != null) {
if (advance == 0) {
} else {
}
}
}
}
```

Now let us test the program:

```package algorithm.linkedlist;

public class Test {

public static void main(String[] args) {
Node head1 = new Node(1);

Node head2 = new Node(3);

TwoNumber twoNumber = new TwoNumber();
}
}
```

Output of the program is:

` →   →  →  →  `

We have used the `reverse` and `print` method from `LinkedListUtil `class for implementing the algorithm.

```package algorithm.linkedlist;

public class LinkedListUtil {

public static Node reverse(Node head) {
if (head == null) {
return null;
}
Node current = head;
Node previous = null;
while (current != null) {
Node next = current.next;
current.next = previous;
previous = current;
current = next;
}
return previous;
}

public static void print(Node head) {
Node temp = head;
while (temp != null) {
temp.print();
temp = temp.next;
}
}

public static void newLine(){
System.out.println();
}
}
```

CORE JAVA ALGORITHM