Add Two Numbers Problem Statement

Write a function which adds two numbers a and b, represented as linked lists of size lenA and lenB respectively, and returns the sum of a and b in the form of a new linked list.

Ignoring the allocation of a new linked list, try to use constant memory when solving it.

A number is represented by a linked list, with the head of the linked list being the least significant digit. For example 125 is represented as 5->2->1, and 371 is represented as 1->7->3. Adding 5->2->1(125) and 1->7->3(371) should produce 6->9->4(496).

Example One

{
"l_a": [7, 5, 2],
"l_b": [2, 0, 3]
}

Output:

[9, 5, 5]

As l_a = 7->5->2 means number 257 and l_b = 2->0->3 means number 302. Sum of 257 and 302 is 559 so, result will represent 9->5->5.

Example Two

{
"l_a": [5, 8, 3],
"l_b": [9, 4, 1]
}

Output:

[4, 3, 5]

As l_a = 5->8->3 means number 385 and l_b = 9->4->1 means number 149. Sum of 385 and 149 is 534 so, result will represent 4->3->5.

Notes

• There are two input parameters l_a and l_b, denoting linked lists representing numbers a and b respectively.
• Output is the head node of resultant linked list representing the sum of two numbers a and b.

Constraints

• 1 <= length of the input linked lists <= 100000
• 0 <= linked list node value <= 9
• Leading zeros will not appear in the input and will not be accepted in the output.
• No negative numbers.

We have provided three solutions. We will refer to the length of l_a and l_b as lenA and lenB, respectively.

Add Two Numbers Solution 1: 1St Other

Let's have a look at an approach for having sum of two numbers x and y represented in decimal number system:

(Let us say string representation of number is num_str, then Least significant digit means digit represented by character at 0th index of num_str and Most significant digit means digit represented by character at len(num_str) - 1-th index of num_str).

• Add trailing zeroes to make the lengths of x and y equal(in decimal system). Let us say this length is N.
• Set carryForward = 0 and i = 0.
• Add i-th significant digit of x and y and add carryForward to it(Let us say this sum sumD). If at i-th significant digit, sumD is greater than 9, we carry forward the tenth place digit of sumD to the next significant digit.
• Set carryForward = sumD/10 and i-th significant digit of result to sumD % 10.
• i = i + 1, Repeat #3 till i <= N - 1.
• If carryForward > 0, set N-th significant digit of result as carryForward.
• Return result.

Now, as numbers are represented as a linked list, with the head of the linked list being the least significant digit, i-th node in linked list will be i-th least significant digit of the number. We need to start traversing linked lists corresponding to given two numbers starting from their heads and follow the above mentioned steps.

In this solution, we are creating an extra linked list to store resultant sum. In an actual interview, ignore the allocation of a new linked list, try to use constant memory when solving it. But if the interviewer asks for the solution which does not modify the input linked lists, then this is the expected solution.

Time Complexity

O(max(lenA, lenB)).

As we are iterating over the given linked list l_a and l_b simultaneously in one iteration. Hence complexity is maximum of length of l_a and length l_b.

Auxiliary Space Used

O(max(lenA, lenB)).

We are storing the resultant sum by creating a new linked list and the size of that newly created linked list can be 1 + max(lenA, lenB).

Space Complexity

O(lenA + lenB).

Space used for input: O(lenA + lenB)

Auxiliary space used: O(max(lenA, lenB))

Space used for output: O(max(lenA, lenB))

So, total space complexity: O(lenA + lenB) + O(max(lenA, lenB)) + O(max(lenA, lenB)) = O(lenA + lenB).

Code For Add Two Numbers Solution 1: 1St Other

    /*
    * Asymptotic complexity in terms of lengths of the first and second number, \`lenA\` and \`lenB\`:
    * Time: O(max(lenA, lenB)).
    * Auxiliary space: O(max(lenA, lenB)).
    * Total space: O(lenA + lenB).
    */
    static LinkedListNode add_two_numbers(LinkedListNode l_a, LinkedListNode l_b) {

        // To store carry while adding two numbers
        int carryForward = 0;
        // Creating another singly linked list to store resultant sum
        LinkedListNode result = new LinkedListNode(-1);
        // To store head of result list, so we can return at the end of function
        LinkedListNode head = result;

        while(l_a != null || l_b != null) {
            int l_a_data = 0;
            if(l_a != null) {
                l_a_data = l_a.value;
                l_a = l_a.next;
            }

            int l_b_data = 0;
            if(l_b != null) {
                l_b_data = l_b.value;
                l_b = l_b.next;
            }

            int sum = l_a_data + l_b_data + carryForward;
            // If it's first node of result linkedlist then update data from -1 to sum % 10.
            if(result.value == -1) {
                result.value = sum % 10;
            }
            else{
                // Create new next node in result linkedlist.
                LinkedListNode new_node = new LinkedListNode(sum % 10);
                result.next = new_node;
                result = result.next;
            }
            carryForward = sum / 10;
        }
        // If still carry is remaining then create another node in result linkedlist to store carry.
        if(carryForward > 0){
            LinkedListNode new_node = new LinkedListNode(carryForward);
            result.next = new_node;
        }
        // Result head node
        return head;
    }

Add Two Numbers Solution 2: 2Nd Other

Approach will be as similar as explained other_solution1, but this approach is bit optimised in terms of space used as we will not create a new linked list to store the resultant sum rather than use one of the linked list l_a or l_b. We are iterating over given two linked lists to find out which one is longer and always making sure that l_b will always be the longer linked list to store the resultant sum if not then by swapping l_a and l_b.

Time Complexity

O(lenA + lenB).

As we are iterating over two given linked lists l_a and l_b. Hence complexity is the sum of their lengths.

Auxiliary Space Used

O(1).

We aren’t storing anything extra and using one of the two given linked list to store the resultant sum.

Space Complexity

O(lenA + lenB).

Space used for input: O(lenA + lenB)

Auxiliary space used: O(1)

Space used for output: O(max(lenA, lenB))

So, total space complexity: O(lenA + lenB) + O(1) + O(max(lenA, lenB)) = O(lenA + lenB).

Code For Add Two Numbers Solution 2: 2Nd Other

    /*
    * Asymptotic complexity in terms of lengths of the first and second number, \`lenA\` and \`lenB\`:
    * Time: O(lenA + lenB).
    * Auxiliary space: O(1).
    * Total space: O(lenA + lenB).
    */
    static LinkedListNode add_two_numbers(LinkedListNode l_a, LinkedListNode l_b) {

        int lenA = 0, lenB = 0;

        // Finding length of l_a
        LinkedListNode travA = l_a;
        while (travA != null) {
            lenA++;
            travA = travA.next;
        }

        // Finding length of l_a
        LinkedListNode travB = l_b;
        while (travB != null) {
            lenB++;
            travB = travB.next;
        }

        // if lenA > lenB, swap linked list pointers, so that after this point onwards,
        // l_a contains smaller length linked list out of given two input linked lists
        if (lenA > lenB) {
            LinkedListNode l_temp = l_a;
            l_a = l_b;
            l_b = l_temp;
        }

        int carryForward = 0;
        travA = l_a;
        travB = l_b;

        while (true) {
            // ith iteration of this loop denotes that we are processing ith significant digit
            int l_a_data = (travA == null) ? 0 : travA.value;

            // let say sumD = travB.value + travA.value + carryForward
            travB.value += l_a_data + carryForward;

            // Setting carryForward = sumD/10
            carryForward = travB.value / 10;

            // In ith iteration, setting ith significant digit of sum = sumD % 10
            travB.value = travB.value % 10;

            // Moving on to (i + 1)th significant digit
            if(travA != null)
                travA = travA.next;

            if (travB.next == null){
                // If carryForward > 0, Adding a node in l_b, which denotes new most significant digit of sum
                // as there is no more digit to carry forward the carryForward
                if (carryForward > 0) {
                    LinkedListNode new_node = new LinkedListNode(carryForward);
                    travB.next = new_node;
                }
                break;
            }
            travB = travB.next;
        }

        return l_b;
    }

Add Two Numbers Solution 3: Optimal

Approach will be as similar as explained other_solution1, but this approach is optimised in terms of number of iterations and extra space used as we are storing the resultant value in one of the given two input linked list only so, we don’t require to create and allocate new linked list.

And we are not finding the longer linked list by iterating over given two linked list as we were doing in other_solution2 but when finding the resultant sum we are changing the pointer and appending the longer list’s remaining nodes to the linked list in which we are storing the resultant sum.

For more detailed explanation refer optimal_solution.

Time Complexity

O(max(lenA, lenB)).

As we are iterating over the given linked list l_a and l_b simultaneously in one iteration. Hence complexity is maximum of length of l_a and length l_b.

Auxiliary Space Used

O(1).

We aren’t storing anything extra and using one of the two given linked lists to store the resultant sum.

Space Complexity

O(lenA + lenB).

Space used for input: O(lenA + lenB)

Auxiliary space used: O(1)

Space used for output: O(max(lenA, lenB))

So, total space complexity: O(lenA + lenB) + O(1) + O(max(lenA, lenB)) = O(lenA + lenB).

Code For Add Two Numbers Solution 3: Optimal

    /*
    * Asymptotic complexity in terms of lengths of the first and second number, \`lenA\` and \`lenB\`:
    * Time: O(max(lenA, lenB)).
    * Auxiliary space: O(1).
    * Total space: O(lenA + lenB).
    */
    static LinkedListNode add_two_numbers(LinkedListNode l_a, LinkedListNode l_b) {

        LinkedListNode result = l_b;
        // We are storing resultant sum in l_b.
        int carryForward = 0, sum = 0;
        // To store carry and current sum.
        // We are iterating till we reach at end of one of linkedlist.
        // and update l_b with resultant sum.
        while(true){
            sum = l_a.value + l_b.value + carryForward;
            l_b.value = sum % 10;
            carryForward = sum / 10;
            if(l_a.next == null || l_b.next == null){
                break;
            }
            l_a = l_a.next;
            l_b = l_b.next;
        }
        // If we reached the end of l_b but not of l_a, we can utilize the already created nodes
        // of l_a by appending them to l_b.
        if(l_a.next != null && l_b.next == null){
            l_b.next = l_a.next;
        }
        // We iterate through remaining nodes of l_b and update it with sum of node and carry.
        while(carryForward > 0 && l_b.next != null){
            l_b = l_b.next;
            sum = carryForward + l_b.value;
            l_b.value = sum % 10;
            carryForward = sum / 10;
        }
        // If still carry is remaining then we add extra node at tail of linkedlist l_b.
        if(carryForward > 0){
            LinkedListNode new_node = new LinkedListNode(carryForward);
            l_b.next = new_node;
        }
        // Result will be head node of l_b (which is storing our resultant sum)
        return result;
    }

We hope that these solutions to add two numbers problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart's FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

• Back-end Engineering Interview Course
• Front-end Engineering Interview Course
• Full Stack Developer Interview Course

‍To learn more, register for the FREE webinar.