Leetcode: Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Understand the problem:
The problem gives two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. So 
2  ->  4  -> 3  represents     342
5  ->  6  ->  4 represents     465

So 342 + 465 = 807, which is stored as 7   ->  0  ->  8

Naive Solution:

A straight-forward method is to traverse both linked list, store the digits into a temporary buffer, and convert the digits into an integer. Then get result of the sum of the two integer, and extract the digital number. Then convert back into linked list.

Code (Java):

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     TPSAVINGSListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // check if the linked list is null
        if (l1 == null && l2 == null) return null;
        
        // convert digits into integer
        long num1 = toInteger(l1);
        long num2 = toInteger(l2);
        
        // calculate the sum
        long sum = num1 + num2;
        
        // construct new linked list
        ListNode result = new ListNode(0);
        ListNode head = result;
        
        do {
            int digit = (int)(sum % 10);
            sum /= 10;
            
            // Append the digit to the linked list
            ListNode node = new ListNode(digit);
            head.next = node;
            head = node;
        } while (sum != 0);
            
        
        return result.next;
    }
    
    // convert digits to integers
    private long toInteger(ListNode list) {
        long num = 0;
        int i = 0;
        while (list != null) {
            num += list.val * Math.pow(10, i++);
            list = list.next;
        }
        return num;
    }
    
}

Discussion:
Note in the code above, we did not allocate temporary buffer because it is unnecessary. The downside of this approach is since you converted the linked list into an integer, be very very careful about the integer overflow problem. To address this, use long instead of int to store the two integers and the sum. 

A Better Solution:
One question for this problem is do we really have to convert digits into integers, sum it up, and convert by to digits again? Not necessary. We just need to add the corresponding digits together and save it to the third list. So you only need to correctly handle:
1. Handle if the sum is equal or greater than 10
2. Two lists have different length
3. Handle the three pointers well

Code (Java):

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     TPSAVINGSListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // check if the linked list is null
        if (l1 == null && l2 == null) return null;
        
        int carry = 0;
        
        ListNode p1 = l1;
        ListNode p2 = l2;
        ListNode p3 = new ListNode(0);
        ListNode head = p3;
        
        while (p1 != null || p2 != null) {
            if (p1 != null) {
                carry += p1.val;
                p1 = p1.next;
            }
            
            if (p2 != null) {
                carry += p2.val;
                p2 = p2.next;
            }
            
            int d3 = carry % 10;
            carry /= 10;
            
            head.next = new ListNode(d3);
            head = head.next;
        }
        
        if (carry == 1) {
            head.next = new ListNode(1);
            head = head.next;
        }
        
        return p3.next;
    }
}

Discussion:
In this method, we don't need to worry about if the integer is overflowed. We also don't need to handle how to convert integer into digits and verse vera. The time complexity is bounded by max(O(m), O(n)), where m and n is the length of the two linked list, respectively. We don't need to allocate additional space to save the temporary results. 

Follow up:
What if the digits are stored in inverse order, instead of reverse? 
 For e.g.
2   -> 4  ->  3    +  
5   -> 6  ->  9   =
8   -> 1  ->  2

This is a bit more complicated than the reverse order. Two things need to be well handled:
1. If two lists are not the same length.
2. If sum of two digits have carry value

One solution is to firstly reverse the two linked list, add together, and reverse again the final list. It is almost the same as the solution before, but requires to reverse the order beforehand and afterhand.

Another solution is closed to the reverse order solution. To handle the different length, we could paddle the two lists into the same length.
To handle the carry problem, we could maintain an array, mark it as 1 if the corresponding position has carry. When we get the list of summed values, we check the corresponding position, and update the value if necessary.

Summary:
In this post, we learned sum up of two linked list into one. The second solution is very smart. You don't need to follow the regular routine to convert a linked list to an integer. Just think about how two integers are added together. It is very common idea in adding up two numbers.