# Write a function that adds the two numbers and returns the sum as a linked list

QUESTION:

Sum Lists: You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1 ‘s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.

EXAMPLE
lnput: (7-> 1 -> 6) + (5 -> 9 -> 2).That is,617 + 295.
Result: : 2 -> 1 -> 9. That is, 912.

Suppose the digits are stored in forwarding order. Repeat the above problem.
Input: (6 -> 1 -> 7) + (2 -> 9 -> 5).That is,617 + 295.
Output: 9 -> 1 -> 2. That is, 912.

SOLUTION:

It’s useful to remember in this problem how exactly addition works. Imagine the problem:

```.wp-block-code {
border: 0;
}

.wp-block-code > div {
overflow: auto;
}

.shcb-language {
border: 0;
clip: rect(1px, 1px, 1px, 1px);
-webkit-clip-path: inset(50%);
clip-path: inset(50%);
height: 1px;
margin: -1px;
overflow: hidden;
position: absolute;
width: 1px;
word-wrap: normal;
word-break: normal;
}

.hljs {
box-sizing: border-box;
}

.hljs.shcb-code-table {
display: table;
width: 100%;
}

.hljs.shcb-code-table > .shcb-loc {
color: inherit;
display: table-row;
width: 100%;
}

.hljs.shcb-code-table .shcb-loc > span {
display: table-cell;
}

.wp-block-code code.hljs:not(.shcb-wrap-lines) {
white-space: pre;
}

.wp-block-code code.hljs.shcb-wrap-lines {
white-space: pre-wrap;
}

.hljs.shcb-line-numbers {
border-spacing: 0;
counter-reset: line;
}

.hljs.shcb-line-numbers > .shcb-loc {
counter-increment: line;
}

.hljs.shcb-line-numbers .shcb-loc > span {
}

.hljs.shcb-line-numbers .shcb-loc::before {
border-right: 1px solid #ddd;
content: counter(line);
display: table-cell;
text-align: right;
-webkit-user-select: none;
-moz-user-select: none;
-ms-user-select: none;
user-select: none;
white-space: nowrap;
width: 1%;
}
```  6 1 7
+ 2 9 5``````
• First, we add 7 and 5 to get 12. The digit 2 becomes the last digit of the number, and 1 gets carried over to the next step.
• Second, we add 1, 1, and 9 to get 11. The 1 becomes the second digit, and the other 1 gets carried over the final step. Third and finally, we add 1, 6 and 2 to get 9. So, our value becomes 912.
• We can mimic this process recursively by adding node by node, carrying over any “excess” data to the next node.
• Let’s walk through this for the below linked list:
``````   7 -> 1 -> 6
+  5 -> 9 -> 2``````

We do the following:

1. We add 7 and 5 first, getting a result of 12. 2 becomes the first node in our linked list, and we “carry” the 1 to the next sum.
List: 2 -> ?
2. We then add 1 and 9, as well as the “carry;’ getting a result of 11. 1 becomes the second element of our
linked list, and we carry the 1 to the next sum.
List: 2 -> 1 ->?
3. Finally, we add 6, 2 and our”carrY:’to get 9. This becomes the final element of our linked list.
List: 2 -> 1 -> 9.

The code below implements this algorithm.

```LinkedListNode addlists(LinkedListNode 11, LinkedListNode 12, int carry) {
if (11 ==·null && 12 == null && carry== 0) {
return null;
}
int value = carry;
if (11 != null) {
value += 11.data;
}
if (12 != null) {
value += 12.data;
}
result.data value% 10; /* Second digit of number */

/*Recurse */

if (11 != null II 12 != null) {
12 == null? null : 12 . next, value>= 10? 1 : 0);
result.setNext(more);
}
return result;
} ```

In implementing this code, we must be careful to handle the condition when one linked list is shorter than another. We don’t want to get a null pointer exception.

Part B is conceptually the same (recurse, carry the excess), but has some additional complications when it comes to implementation:

1. One list may be shorter than the other, and we cannot handle this “on the flY:’ For example, suppose we
were adding (1 -> 2 -> 3-> 4) and (5-> 6-> 7). We need to know that the 5 should be”matched”with the
2, not the 1. We can accomplish this by comparing the lengths of the lists in the beginning and padding
the shorter list with zeros.
2. In the first part, successive results were added to the tail (i.e., passed forward). This meant that the recur
sive call would be passed the carry, and would return the result (which is then appended to the tail). In
this case, however, results are added to the head (i.e., passed backward). The recursive call must return
the result, as before, as well as the carry. This is not terribly challenging to implement, but it is more
cumbersome. We can solve this issue by creating a wrapper class called Partial Sum.

The code below implements this algorithm.

```class PartialSum {
public int carry= 0;
}
int lenl length(ll);
int len2 = length(l2);

/* Pad the shorter list with zeros - see note (1) */
if (lenl < len2) {
l1 = padlist(ll, len2 - lenl);
} else {
l2 = padlist(l2, lenl - len2);
}

/* If there was a carry value left over, insert this at the front of the list.
21 * Otherwise, just return the linked list. */

if (sum.carry== 0) {
return sum.sum;
} else {
return result;
}
}
if (11 == null && 12 == null) {
Partia1Sum sum= new Partia1Sum();
return sum;
}

/* Add carry to current data*/
int val= sum.carry + 11.data + 12.data;

/* Insert sum of current digits*/
LinkedListNode full_result = insertBefore(sum.sum, val% 10);

/* Return sum so far, and the carry value*/
sum.sum= full_result;
sum.carry val/ 10;
return sum;
}

/* Pad the list with zeros*/
for (int i= 0; i < padding; i++) {
}