Add Two Numbers

The question: You are given two non-empty linked lists, representing two non-negative numbers. The digits are stored in the reverse order, each node holds just one digit. The task to add the two numbers and return the solution in the form a linked list, again, digits stored in the reverse order. You can assume that there are no leading zeroes.

Example: (2->3->4) + (2->1->3) [i.e., 432 + 312]

Expected Solution: (4->4->7) [i.e., 432 + 312 = 744]

Initial thoughts:

1. Should we construct the numbers first, compute the sum and transform the sum into the linked list to be returned as the solution? Well, that’s definitely not an efficient solution.
2. So, considering the efficiency, probably a good approach would be to work with a single loop to traverse through both the linked lists at a time.

Approach 1:

This is a problem with a difficulty level as medium. Therefore, it makes sense to build the solution in steps and improvising it as we go. By this point we have established that we will be using a looping statement, to traverse through the lists(both the lists at the same time). This loop is likely to be running as long as the nodes in the longest list is exhausted. Wait a minute — if there is a carry over, we need to run an extra iteration to account for that as well.

Note: The result is also going to a LinkedList with the digits of the final sum stored in the reverse order. That means we need one LinkedList that will be returned as the result pointing to the digit at the units position. And another copy which will be used to traverse through and store the sum of the current node position. This latter list will be the one that is used to for the actual computation.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int digitFromFirst;
        int digitFromSecond;
        int carryOver = 0;
        ListNode output = null;
        ListNode previousNode = null;
        while(l1!=null || l2!=null || carryOver!=0){
            digitFromFirst = digitFromSecond = 0;
            if(l1!=null){
                digitFromFirst = l1.val;
                l1 = l1.next;
            }
            if(l2!=null){
                digitFromSecond = l2.val;
                l2 = l2.next;
            }
            int currentSum = carryOver + digitFromFirst + digitFromSecond;
            if(output == null){
                output = new ListNode(currentSum%10);
                previousNode = output;
            } else {
                ListNode currentNode = new ListNode(currentSum%10);
                previousNode.next = currentNode;
                previousNode = currentNode;
            }
            carryOver = currentSum/10;
        }
        return output;
    }

Find more posts here.

Cheers & Chao!