LeetCode 2. Add Two Numbers (Problem: https://leetcode.com/problems/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…

AddTwoNumbers.java

/**
 * LeetCode 2. Add Two Numbers (Problem Link: https://leetcode.com/problems/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
 */

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class AddTwoNumbers {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        
        // Save head pointer to the result list
        ListNode safeHead = new ListNode(-1);
        
        ListNode tracker1 = l1;
        ListNode tracker2 = l2;
        ListNode resultTracker = safeHead;
        int carry = 0;
        int currentSum = 0;
        
        /** 
         * NOTE: 
         * Following approach carries repeated code with multiple loops but is slightly 
         * faster than code with a single while loop and frequent null checks for tracker1 and tracker2.
         * 
         * Sample run-time of 1556 tests on leetcode's Online Judge:
         * With a single loop: 5ms (beats 5.87% of Java submissions)
         * With multiple loops: 4ms (beats 31.63% of Java submissions)
         */
        
        // Traverse till both lists have digits
        while(tracker1 != null && tracker2 != null){
            currentSum = carry + tracker1.val + tracker2.val;
            carry = currentSum / 10;
            currentSum = currentSum % 10;
            // Save the resulting digit as a new node in result list
            resultTracker.next = new ListNode(currentSum);
            resultTracker = resultTracker.next;
            tracker1 = tracker1.next;
            tracker2 = tracker2.next;
        }
        
        // Copy over the remaining digits of the list yet to be traversed fully
        if(tracker1 == null){
            while(tracker2 != null){
                currentSum = carry + tracker2.val;
                carry = currentSum / 10;
                currentSum = currentSum % 10;
                // Save the resulting digit as a new node in result list
                resultTracker.next = new ListNode(currentSum);
                resultTracker = resultTracker.next;
                tracker2 = tracker2.next;
            }
        }
        else{
            while(tracker1 != null){
                currentSum = carry + tracker1.val;
                carry = currentSum / 10;
                currentSum = currentSum % 10;
                // Save the resulting digit as a new node in result list
                resultTracker.next = new ListNode(currentSum);
                resultTracker = resultTracker.next;
                tracker1 = tracker1.next;
            }
        }
        
        // At the end if carry is still non-zero, create a new digit for it
        if(carry > 0){
            resultTracker.next = new ListNode(carry);
            resultTracker = resultTracker.next;
        }
        
        // Return the head of result list
        return safeHead.next;
    }
}