Add Two Numbers As Linked Lists
You are given two linked lists representing two non-negative numbers. The digits in the linked list are stored in reverse order, i.e. starting from least significant digit (LSD) to the most significant digit (MSD), and each of their nodes contains a single digit. Your task is to find the sum list and return the head of the sum list where the sum list is a linked list representation of the addition of two numbers.

Note :

The number represented by the linked lists do not contain any leading zeros.

Input Format:

The first line of input contains a single integer T, representing the number of test cases. Then the T test cases follow. The first line of each test case contains the elements of the first singly linked list separated by a single space and terminated by -1. The second line of each test case contains the elements of the second singly linked list separated by a single space and terminated by -1.

Output Format:

For each test case, print the sum linked list. The elements of the sum list should be single-space separated and terminated by -1. The output of each test case must be printed on a separate line.

Note :

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints :

1

Question

Add Two Numbers As Linked Lists

You are given two linked lists representing two non-negative numbers. The digits in the linked list are stored in reverse order, i.e. starting from least significant digit (LSD) to the most significant digit (MSD), and each of their nodes contains a single digit. Your task is to find the sum list and return the head of the sum list where the sum list is a linked list representation of the addition of two numbers.

Note :

The number represented by the linked lists do not contain any leading zeros.

Input Format:

The first line of input contains a single integer T, representing the number of test cases. 

Then the T test cases follow.

The first line of each test case contains the elements of the first singly linked list separated by a single space and terminated by -1.

The second line of each test case contains the elements of the second singly linked list separated by a single space and terminated by -1.

Output Format:

For each test case, print the sum linked list. The elements of the sum list should be single-space separated and terminated by -1.

The output of each test case must be printed on a separate line.

Note :

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= M, N <= 5 * 10^4
0 <= data[i] <= 9 and data[i] != -1

Where 'M' and 'N' are the number of nodes in the two linked lists, 'data[i]' is the data of the 'i-th' node.

Time Limit: 1 sec

Accepted Answer

Recursion

A simple approach could be to recursively add the nodes of the linked list while keeping track of the carry generated.
The idea behind this approach is the same as finding the sum of two numbers manually on a paper, where we start by adding the LSD and move on till the MSD. Also, keeping track of the carry generated in every iteration.
As the linked lists represent the numbers in reverse order, the LSD occurs at the starting of the list and MSD occurs at the ending.
So to perform the addition, we can add the corresponding nodes (i.e. nodes present at the same position) of the two linked lists to generate the resulting digit in the sum list.
While adding, it is possible that the sum of the two nodes is greater than 9. This will generate a carry that needs to be added to the next significant digit.
In case one of the lists has more number elements than the other, then we consider the remaining values of the other list as 0.

The steps are as follows:

Let the recursive function be addTwoNumbersHelper('NODE1', 'NODE2', 'CARRY') which takes the current node of the first list, the current node of the second list, and the carry generated from the previous iteration/addition.
Initially, we call the function as addTwoNumbersHelper('HEAD1', 'HEAD2', 0).
Base Condition: If 'NODE1' = NULL AND 'NODE2' = NULL AND 'CARRY' = 0, return NULL.
Let 'VAL1' and 'VAL2' denote the value stored in the current nodes of the two linked lists, respectively. And 'NEXT_1' and 'NEXT_2' denote the pointers to the node present after the current nodes of the two linked lists, respectively.
If 'NODE1' = NULL, then the list 1 is empty so consider the current node’s value as zero i.e. 'VAL1' = 0, and the node after the current node as NULL i.e. 'NEXT_1' = NULL.
Otherwise, list 1 is not empty. So, 'VAL1' = 'NODE1'.data and 'NEXT_1' = 'NODE1'.next.
If 'NODE2' = NULL, then the list 2 is empty so consider the current node’s value as zero i.e. 'VAL2' = 0 and the node after the current node as NULL i.e. 'NEXT_2' = NULL. .
Otherwise, list 2 is not empty. So, 'VAL2' = 'NODE2'.data and 'NEXT_2' = 'NODE2'.next.
Add the values in the current nodes of the two linked lists along with the carry to generate the resulting sum. Store it in a variable, say sum i.e. 'SUM' = 'VAL1' + 'VAL2' + 'CARRY'.
Get the next node of the sum list by creating a new node having data = 'SUM'%10. Store the new node in a variable say, 'SUM_NODE'.
Recursively call the function to generate the remaining nodes of the sum list as:
- 'SUM_NODE'.next = addTwoNumbersHelper('NEXT_1', 'NEXT_2', 'SUM'/10)
Return 'SUM_NODE'.

Space Complexity: OtherExplanation:

O(Max(M, N)), where M and N are the number of nodes in the two linked lists.

Extra space is required for the recursion stack and also for storing the sum list. The maximum depth of the stack is O(Max(M, N)). Also, the length of the sum list is O(Max(M, N)). Hence, the overall space complexity is O(Max(M, N)).

Time Complexity: OtherExplanation:

O(M + N), where M and N are the number of nodes in the two linked lists.

We are traversing both the linked lists completely and it takes O(L) (where L is the number of nodes in the list) time to traverse each list. Hence, the overall time complexity is O(M+N).

Python (3.5)

'''
    Time Complexity - O(M + N)
    Space Complexity - O(Max(M, N))

    Where 'M' and 'N' are the number of nodes in the two linked lists.
'''


class Node:
    def __init__(self, data):

        self.data = data
        self.next = None

    def __del__(self):
        if(self.next):
            del self.next


def addTwoNumbersHelper(node1, node2, carry):
    if (node1 == None and node2 == None and carry == 0):
        # Added both the lists and no carry is generated.
        return None

    '''
        'VAL1' and 'VAL2' store the data of the current nodes of the two linked lists.
        'NEXT1' and 'NEXT2' point to the node present after the current nodes of the two linked lists.
    '''
    if(node1 == None):
        # List 1 is empty. So, consider the current node's value as zero.
        val1 = 0
        # And the node after the current node as NULL.
        next1 = None
    else:
        val1 = node1.data
        next1 = node1.next

    if(node2 == None):
        # List 2 is empty. So, consider the current node's value as zero.
        val2 = 0
        # And the node after the current node as NULL.
        next2 = None
    else:
        val2 = node2.data
        next2 = node2.next

    # Add the values in the current nodes along with the carry.
    sum = val1 + val2 + carry

    # Create the next node of the sum list.
    sumNode = Node(sum % 10)

    # Recursively call the function to generate the remaining nodes of the sum list.
    sumNode.next = addTwoNumbersHelper(next1, next2, sum // 10)

    return sumNode


def addTwoNumbers(head1, head2):
    return addTwoNumbersHelper(head1, head2, 0)

Java (SE 1.8)

/*

    Time Complexity - O(M + N)

    Space Complexity - O(Max(M, N))



    Where 'M' and 'N' are the number of nodes in the two linked lists.

*/





public class Solution{



    static LinkedListNode addTwoNumbersHelper(LinkedListNode node1, LinkedListNode node2, int carry)

    {

        if (node1 == null && node2 == null && carry == 0)

        {

            // Added both the lists and no carry is generated.

            return null;

        }



        // 'VAL1' and 'VAL2' store the data of the current nodes of the two linked lists.

        int val1, val2;



        // 'NEXT1' and 'NEXT2' point to the node present after the current nodes of the two linked lists.

        LinkedListNode next1, next2;



        if (node1 == null)

        {

            // List 1 is empty. So, consider the current node's value as zero.

            val1 = 0;

            // And the node after the current node as null.

            next1 = null;

        }

        else

        {

            val1 = node1.data;

            next1 = node1.next;

        }



        if (node2 == null)

        {

            // List 2 is empty. So, consider the current node's value as zero.

            val2 = 0;

            // And the node after the current node as null.

            next2 = null;

        }

        else

        {

            val2 = node2.data;

            next2 = node2.next;

        }



        // Add the values in the current nodes along with the carry.

        int sum = val1 + val2 + carry;



        // Create the next node of the sum list.

        LinkedListNode sumNode = new LinkedListNode(sum % 10);



        // Recursively call the function to generate the remaining nodes of the sum list.

        sumNode.next = addTwoNumbersHelper(next1, next2, sum / 10);



        return sumNode;

    }





    static LinkedListNode addTwoNumbers(LinkedListNode head1, LinkedListNode head2)

    {

        return addTwoNumbersHelper(head1, head2, 0);

    }

}

C++ (g++ 5.4)

/*

    Time Complexity - O(M + N)

    Space Complexity - O(Max(M, N))



    Where 'M' and 'N' are the number of nodes in the two linked lists.

*/



Node *addTwoNumbersHelper(Node *node1, Node *node2, int carry)

{

    if (node1 == NULL && node2 == NULL && carry == 0)

    {

        // Added both the lists and no carry is generated.

        return NULL;

    }



    // 'VAL1' and 'VAL2' store the data of the current nodes of the two linked lists.

    int val1, val2;



    // 'NEXT1' and 'NEXT2' point to the node present after the current nodes of the two linked lists.

    Node *next1, *next2;



    if (node1 == NULL)

    {

        // List 1 is empty. So, consider the current node's value as zero.

        val1 = 0;

        // And the node after the current node as NULL.

        next1 = NULL;

    }

    else

    {

        val1 = node1->data;

        next1 = node1->next;

    }



    if (node2 == NULL)

    {

        // List 2 is empty. So, consider the current node's value as zero.

        val2 = 0;

        // And the node after the current node as NULL.

        next2 = NULL;

    }

    else

    {

        val2 = node2->data;

        next2 = node2->next;

    }



    // Add the values in the current nodes along with the carry.

    int sum = val1 + val2 + carry;



    // Create the next node of the sum list.

    Node *sumNode = new Node(sum % 10);



    // Recursively call the function to generate the remaining nodes of the sum list.

    sumNode->next = addTwoNumbersHelper(next1, next2, sum / 10);



    return sumNode;

}



Node *addTwoNumbers(Node *head1, Node *head2)

{

    return addTwoNumbersHelper(head1, head2, 0);

}

Accepted Answer

Iterative Approach

The idea behind this approach is exactly similar to the previous approach. But here, instead of using recursion, we add the two linked lists iteratively.

The steps are as follows:

Let 'NODE1' and 'NODE2' denote the current node of the first list and the second list, respectively.
Initially, 'NODE1' = 'HEAD1' and 'NODE2' = 'HEAD2'
Create two variables ‘SUM’ and 'CARRY' which will be used to store the sum and carry generated in the current iteration and initialize them with zero.
Repeat the following steps until both the lists are exhausted i.e. 'NODE1' != NULL OR 'NODE2' != NULL:
- Set 'SUM' = 'CARRY'.
- If 'NODE1' != NULL, then list 1 is not exhausted. So, add the current node’s value to the sum i.e. 'SUM' = 'SUM' + 'NODE1'.data. And move to the next node of the list i.e. 'NODE1' = 'NODE1'.next.
- If 'NODE2' != NULL, then list 2 is not exhausted. So, add the current node’s value to the sum i.e. 'SUM' = 'SUM' + 'NODE2'.data. And move to the next node of the list i.e. 'NODE2' = 'NODE2'.next.
- Get the next node of the sum list by creating a new node having data = 'SUM' % 10. And add this node to the sum list.
- Set 'CARRY' = 'SUM'/10.
If 'CARRY' = 1, add a new node to the sum list having data = 1.
Return the head of the sum list i.e ‘HEAD1’.

Space Complexity: OtherExplanation:

O(Max(M, N)), where M and N are the number of nodes in the two linked lists.

Extra space is required for storing the sum list. The length of the sum list is O(Max(M, N)). Hence, the overall space complexity is O(Max(M, N)).

Time Complexity: OtherExplanation:

O(M + N), where M and N are the number of nodes in the two linked lists.

We are traversing both the linked lists completely and it takes O(L) (where L is the number of nodes in the list) time to traverse each list. Hence, the overall time complexity is O(M+N).

Python (3.5)

'''

    Time Complexity - O(M + N)

    Space Complexity - O(Max(M, N))



    Where 'M' and 'N' are the number of nodes in the two linked lists.

'''





class Node:

    def __init__(self, data):



        self.data = data

        self.next = None



    def __del__(self):

        if(self.next):

            del self.next





def addTwoNumbers(head1, head2):

    # 'NODE1' and 'NODE2' point to the current node of the first and second list, respectively.

    node1 = head1

    node2 = head2



    # 'SUMHEAD' stores the head of the sum list.

    sumHead = None



    prev = None



    # 'SUM' and 'CARRY' store the sum and carry generated in the current iteration.

    sum = carry = 0



    while(node1 != None or node2 != None):

        sum = carry



        if(node1 != None):

            # Add the current node's value to the sum.

            sum += node1.data



            # Move to the next node of the list 1.

            node1 = node1.next



        if(node2 != None):

            # Add the current node's value to the sum.

            sum += node2.data



            # Move to the next node of the list 2.

            node2 = node2.next



        # Create the next node of the sum list.

        sumNode = Node(sum % 10)



        # Add the node to the sum list.

        if (sumHead == None):

            # Node generated is the first node. So, update the head of sum list.

            sumHead = sumNode

        else:

            # Add the node to the end of the list.

            prev.next = sumNode



        prev = sumNode



        # Get the new carry.

        carry = sum // 10



    if(carry > 0):

        # Carry is generated from the last iteration. So, add a new node.

        prev.next = Node(carry)



    return sumHead

Java (SE 1.8)

/*

    Time Complexity - O(M + N)

    Space Complexity - O(1)



    Where 'M' and 'N' are the number of nodes in the two linked lists.

*/





public class Solution{



    static LinkedListNode addTwoNumbers(LinkedListNode head1, LinkedListNode head2)

    {

        // 'NODE1' and 'NODE2' point to the current node of the first and second list, respectively.

        LinkedListNode node1 = head1;

        LinkedListNode node2 = head2;



        // 'SUMHEAD' stores the head of the sum list.

        LinkedListNode sumHead = null;



        LinkedListNode sumNode, prev = null;



        // 'SUM' and 'CARRY' store the sum and carry generated in the current iteration.

        int sum = 0, carry = 0;



        while (node1 != null || node2 != null)

        {

            sum = carry;



            if (node1 != null)

            {

                // Add the current node's value to the sum.

                sum += node1.data;



                // Move to the next node of the list 1.

                node1 = node1.next;

            }



            if (node2 != null)

            {

                // Add the current node's value to the sum.

                sum += node2.data;



                // Move to the next node of the list 2.

                node2 = node2.next;

            }



            // Create the next node of the sum list.

            sumNode = new LinkedListNode(sum % 10);



            // Add the node to the sum list.

            if (sumHead == null)

            {

                // Node generated is the first node. So, update the head of sum list.

                sumHead = sumNode;

            }

            else

            {

                // Add the node to the end of the list.

                prev.next = sumNode;

            }

            prev = sumNode;



            // Get the new carry.

            carry = sum / 10;

        }



        if (carry > 0)

        {

            // Carry is generated from the last iteration. So, add a new node.

            prev.next = new LinkedListNode(carry);

        }



        return sumHead;

    }

}

C++ (g++ 5.4)

/*

    Time Complexity - O(M + N)

    Space Complexity - O(Max(M, N))



    Where 'M' and 'N' are the number of nodes in the two linked lists.

*/



Node *addTwoNumbers(Node *head1, Node *head2)

{

    // 'NODE1' and 'NODE2' point to the current node of the first and second list, respectively.

    Node *node1 = head1;

    Node *node2 = head2;



    // 'SUMHEAD' stores the head of the sum list.

    Node *sumHead = NULL;



    Node *sumNode, *prev = NULL;



    // 'SUM' and 'CARRY' store the sum and carry generated in the current iteration.

    int sum = 0, carry = 0;



    while (node1 != NULL || node2 != NULL)

    {

        sum = carry;



        if (node1 != NULL)

        {

            // Add the current node's value to the sum.

            sum += node1->data;



            // Move to the next node of the list 1.

            node1 = node1->next;

        }



        if (node2 != NULL)

        {

            // Add the current node's value to the sum.

            sum += node2->data;



            // Move to the next node of the list 2.

            node2 = node2->next;

        }



        // Create the next node of the sum list.

        sumNode = new Node(sum % 10);



        // Add the node to the sum list.

        if (sumHead == NULL)

        {

            // Node generated is the first node. So, update the head of sum list.

            sumHead = sumNode;

        }

        else

        {

            // Add the node to the end of the list.

            prev->next = sumNode;

        }

        prev = sumNode;



        // Get the new carry.

        carry = sum / 10;

    }



    if (carry > 0)

    {

        // Carry is generated from the last iteration. So, add a new node.

        prev->next = new Node(carry);

    }



    return sumHead;

}

Accepted Answer

Observation for Space Optimization

The idea behind this approach is exactly similar to the previous approach. But here, instead of creating a new list for storing the sum, we use any one of the two linked lists to store the sum list.
Note: Here we have used the first linked list to store the sum list. We can also use the second list but the idea will remain the same.

The Steps are as follows:

Let 'NODE1' and 'NODE2' denote the current node of the first list and the second list, respectively.
Initially, 'NODE1' = 'HEAD1' and 'NODE2' = 'HEAD2'
Create two variables ‘SUM’ and ‘CARRY’ which will be used to store the sum and carry generated in the current iteration and initialize them with zero.
Create another variable 'PREV' to store the previous node of the linked list, and initialize it with NULL.
Repeat the following steps until any one the lists is exhausted i.e. 'NODE1' != NULL AND 'NODE2' != NULL:
- Add the values in the current nodes of the two linked lists along with the carry to generate the resulting sum i.e. ‘SUM’ = 'NODE1'.data + 'NODE2'.data + 'CARRY'.
- Store the next node of the sum list in the first linked list by updating the current node’s data value as 'NODE1'.data = ‘SUM’ % 10.
- Update the carry as 'CARRY' = ‘SUM’ / 10.
- Keep track of the previous node by setting 'PREV' = 'NODE1'.
- Move to the next node:
  - 'NODE1' = 'NODE1'.next
  - 'NODE2' = 'NODE2'.next
Check any of list contain the remaining digits, i.e. if 'NODE1' != NULL OR 'NODE2' != NULL:
- We need to add the remaining digits to the sum list.
- If 'NODE2' != NULL, list 1 is empty and list 2 contains the remaining digits. So, set 'PREV'.next = 'NODE2'.
- Set, 'NODE1' = 'PREV'.next.
- Add the remaining digits to the sum list by repeating the following operation until 'NODE1' becomes NULL:
  - ‘SUM’ = 'NODE1'.data + 'CARRY'
  - Store the next digit by updating the current node’s data value 'NODE1'.data = ‘SUM’ % 10.
  - Update the carry as 'CARRY' = ‘SUM’ / 10.
  - Keep track of the previous node by setting 'PREV' = 'NODE1'.
  - Move to the next node, 'NODE1' = 'NODE1'.next
Now, we have added both lists. But it is possible that carry is generated from the last iteration. So, if 'CARRY' = 1, add a new node to the sum list having data = 1.
Return the head of the sum list i.e. 'HEAD1'.

Space Complexity: O(1)Explanation:

O(1)

In the worst case, only one new node needs to be created i.e. when the sum generates a carry. Hence, the overall space complexity is O(1).

Time Complexity: OtherExplanation:

O(M + N), where M and N are the number of nodes in the two linked lists.

We are traversing both the linked lists completely and it takes O(L) (where L is the number of nodes in the list) time to traverse each list. Hence, the overall time complexity is O(M+N).

C++ (g++ 5.4)

/*

    Time Complexity - O(M + N)

    Space Complexity - O(1)



    Where 'M' and 'N' are the number of nodes in the two linked lists.

*/



Node *addTwoNumbers(Node *head1, Node *head2)

{

    // 'NODE1' and 'NODE2' point to the current node of the first and second list, respectively.

    Node *node1 = head1;

    Node *node2 = head2;



    // 'SUM' and 'CARRY' store the sum and carry generated in the current iteration.

    int sum = 0, carry = 0;



    Node *prev = NULL;



    while (node1 != NULL && node2 != NULL)

    {

        // Add the values in the current nodes along with the carry.

        sum = node1->data + node2->data + carry;



        // Store the next node of the sum list in the current node of the first linked list.

        node1->data = sum % 10;



        // Get the new carry.

        carry = sum / 10;



        // Keep track of the previous node.

        prev = node1;



        // Move to the next node

        node1 = node1->next;

        node2 = node2->next;

    }



    // If there are remaining digits in any one of the lists, add them to the sum list.

    if (node1 != NULL || node2 != NULL)

    {

        if (node2 != NULL)

        {

            prev->next = node2;

        }



        node1 = prev->next;



        while (node1 != NULL)

        {

            // Add the values in the current node along with the carry.

            sum = node1->data + carry;



            // Store the next node of the sum list in the current node of the first linked list.

            node1->data = sum % 10;



            // Get the new carry.

            carry = sum / 10;



            // Keep track of the previous node.

            prev = node1;



            // Move to the next node

            node1 = node1->next;

        }

    }



    if (carry > 0)

    {

        // Carry is generated from the last iteration. So, add a new node to the sum list.

        prev->next = new Node(carry);

    }



    // Return the head of the sum list.

    return head1;

}

Java (SE 1.8)

/*

    Time Complexity - O(M + N)

    Space Complexity - O(1)



    Where 'M' and 'N' are the number of nodes in the two linked lists.

*/





public class Solution{



    static LinkedListNode addTwoNumbers(LinkedListNode head1, LinkedListNode head2)

    {

        // 'NODE1' and 'NODE2' point to the current node of the first and second list, respectively.

        LinkedListNode node1 = head1;

        LinkedListNode node2 = head2;



        // 'SUM' and 'CARRY' store the sum and carry generated in the current iteration.

        int sum = 0, carry = 0;



        LinkedListNode prev = new LinkedListNode(-1);



        while (node1 != null && node2 != null)

        {

            // Add the values in the current nodes along with the carry.

            sum = node1.data + node2.data + carry;



            // Store the next node of the sum list in the current node of the first linked list.

            node1.data = sum % 10;



            // Get the new carry.

            carry = sum / 10;



            // Keep track of the previous node.

            prev = node1;



            // Move to the next node

            node1 = node1.next;

            node2 = node2.next;

        }



        // If there are remaining digits in any one of the lists, add them to the sum list.

        if (node1 != null || node2 != null)

        {

            if (node2 != null)

            {

                prev.next = node2;

            }



            node1 = prev.next;



            while (node1 != null)

            {

                // Add the values in the current node along with the carry.

                sum = node1.data + carry;



                // Store the next node of the sum list in the current node of the first linked list.

                node1.data = sum % 10;



                // Get the new carry.

                carry = sum / 10;



                // Keep track of the previous node.

                prev = node1;



                // Move to the next node

                node1 = node1.next;

            }

        }



        if (carry > 0)

        {

            // Carry is generated from the last iteration. So, add a new node to the sum list.

            prev.next = new LinkedListNode(carry);

        }



        return head1;

    }

}

Python (3.5)

'''

    Time Complexity - O(M + N)

    Space Complexity - O(1)



    Where 'M' and 'N' are the number of nodes in the two linked lists.

'''





class Node:

    def __init__(self, data):



        self.data = data

        self.next = None



    def __del__(self):

        if(self.next):

            del self.next





def addTwoNumbers(head1, head2):

    # 'NODE1' and 'NODE2' point to the current node of the first and second list, respectively.

    node1 = head1

    node2 = head2



    prev = None



    # 'SUM' and 'CARRY' store the sum and carry generated in the current iteration.

    sum = carry = 0



    while(node1 != None and node2 != None):

        # Add the values in the current nodes along with the carry.

        sum = node1.data + node2.data + carry



        # Store the next node of the sum list in the current node of the first linked list.

        node1.data = sum % 10



        # Get the new carry.

        carry = sum // 10



        # Keep track of the previous node.

        prev = node1



        # Move to the next node

        node1 = node1.next

        node2 = node2.next



    # If there are remaining digits in any one of the lists, add them to the sum list.

    if(node1 != None or node2 != None):

        if (node2 != None):

            prev.next = node2



        node1 = prev.next



        while(node1 != None):

            # Add the values in the current node along with the carry.

            sum = node1.data + carry



            # Store the next node of the sum list in the current node of the first linked list.

            node1.data = sum % 10



            # Get the new carry.

            carry = sum // 10



            # Keep track of the previous node.

            prev = node1



            # Move to the next node

            node1 = node1.next



    if(carry > 0):

        # Carry is generated from the last iteration. So, add a new node.

        prev.next = Node(carry)



    # Return the head of the sum list.

    return head1

Note :

Input Format:

Output Format:

Note :

Constraints :

Top TCS Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in TCS Software Developer