LeetCode: 2. Add Two Numbers

LeetCode Prompt:

/** This prompt belongs to LeetCode **/

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

You really have to read this prompt a few times before letting it sink in. I think the most overlooked detail is that “The digits are stored in reverse order….” This is an incredibly important detail because it makes the algorithm a lot more simple; we don’t have to do any backwards carrying. In other words, 2 -> 4 -> 3 really represents the number ‘342’ and so forth for every other ListNode.

Here is the code I came up with:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode tmpL1 = l1;
        ListNode tmpL2 = l2;
        int carryOver = 0;
        while(tmpL1 != null && tmpL2 != null){
            tmpL1.val = tmpL1.val + tmpL2.val + carryOver;
            if(tmpL1.val >= 10){
                carryOver = 1;
                tmpL1.val -= 10;
                if(tmpL1.next == null && tmpL2.next == null){
                    tmpL1.next = new ListNode(carryOver);
                    return l1;
                }
            } else {
                carryOver = 0;
            }
            
            if(tmpL1.next == null && tmpL2.next != null){
                tmpL1.next = new ListNode(0);
            }
            if(tmpL1.next != null && tmpL2.next == null){
                tmpL2.next = new ListNode(0);
            }
            
            tmpL1 = tmpL1.next;
            tmpL2 = tmpL2.next;
            
        }
        return l1;
    }
}

This code is simply iterating over every entry in the first and second ListNode and adding the values together. Following this, the algorithm checks if the summation is greater than or equal to 10 which denotes that we need to carry to the right. Since we only have to deal with digits, the max summation can only total 18 which means that the max carry over is 1. We have to do some conditional checking regarding null pointers due to uneven sizes of the ListNode.

See any improvements to make this faster? Comment below!

Leave a Reply

Your email address will not be published.