Solving The Add Two Numbers Leetcode Question

Question

You are given the starting nodes of two LinkedLists. Each LinkedList represents a reversed integer value: that is the value 768 is represent in linked list form as 8->6->7. The task is to add the numbers in the linked list and then return the head of a new linked list representing the sum with the numbers reversed.

Clarifying Questions

• Are the values of the ListNodes between 0 and 9? This question is important because we want to keep track of carry values after addition.

• What are the maximum values represented by a LinkedList? This question is important because we want to it would determined the approach to take. If the maximum values represented by a linkedlist can be the INTEGER.MAX_VALUE then this means that we cannot "integerify" both linked lists and then convert the result to a list and then return the head.

• Do both input lists have the same number of nodes? This question would determine the constraints in your solution.

Approach 1: Brute Force

The brute force approach to solving this is "integerify" both input lists, add the resulting integers and then finally convert the sum to a list.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int l1Str = convertToInt(l1);
        int l2Str = convertToInt(l2);
        int sum = l1Str + l2Str;
        ListNode result = convertToList(sum);
        return result;
    }

    private ListNode convertToList(int num){
        ListNode head = new ListNode(num%10);
        num = num/10;
        ListNode current = head;
        while (num>0){
            current.next = new ListNode(num%10);
            num = num/10;
            current = current.next;
        }
        return head;
    }

    private int convertToInt(ListNode l) {
        ListNode current = l;
        StringBuilder sb = new StringBuilder();
        while (current!= null) {
            sb.append(current.val);
            current = current.next;
        }
        return Integer.parseInt(sb.reverse().toString());
    }
}

The time complexity for this solution is O(max(N,M)) and space complexity is O(n). However this solution fails for the edge case 9999999991 and 9 because 9999999991 overflows the java integer data type.

Approach 2:

My second approach was to traverse both lists and add the corresponding digits individually. This meant that I needed to track the carry (most significant digit after every addition), while I create a new list node with the least significant digit as the val. I created two ListNode variables one to keep track of the result and the other to keep track of the current additions.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int carry = 0;
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        while (l1 != null || l2 != null || carry != 0) {
            int l1Val = l1 != null ? l1.val : 0;
            int l2Val = l2 != null ? l2.val : 0;
            int sum = l1Val + l2Val + carry;
            current.next = new ListNode(sum%10);
            carry = sum/10;
            current = current.next;
            if (l1 != null){
                l1 = l1.next; 
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        return dummy.next;
    }
}

Time Complexity: O(max(n,m))

Space Complexity: O(n)