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

by

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.

FOLLOW UP
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:

  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;
}
LinkedlistNode result new LinkedlistNode();
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) {
LinkedlistNode more = addlists(ll == null ? null : 11.next,
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.

Follow Up

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 LinkedListNode sum = null;
public int carry= 0;
}
LinkedlistNode addLists(LinkedListNode 11, LinkedListNode 12) {
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);
}

/* Add lists */
PartialSum sum = addListsHelper(ll, 12);

/* 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 {
LinkedListNode result insertBefore(sum.sum, sum.carry);
return result;
}
}
Partia1Sum addListsHelper(LinkedListNode 11, LinkedlistNode ) {
if (11 == null && 12 == null) {
Partia1Sum sum= new Partia1Sum();
return sum;
 }

/* Add smaller digits recursively*/
Partia1Sum sum= addListsHelper(ll.next, 12.next);

/* 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*/
LinkedListNode padList(LinkedListNode 1, int padding) {
LinkedlistNode head= l;
for (int i= 0; i < padding; i++) {
head= insertBefore(head, 0);
}
return head;
}

/* Helper function to insert node in the front of a linked list*/
LinkedListNode insertBefore(LinkedListNode list, int data) {
LinkedListNode node= new LinkedListNode(data);
if (list != null) {
node.next= list;
}
return node;
}
  • Note how we have pulled insertBefore(), padlist(), and length() (not listed) into their own methods.
  • This makes the code cleaner and easier to read-a a wise thing to do in your interviews!

Leave a Comment