Sum of Two Linked Lists using Recursion | Set 1

Given two numbers which are represented using linked lists as shown below. Return the reference to a new linked list which stores the sum of given two numbers. You are not allowed to make use of explicit extra space except temporary variables.

Numbers are represented as following:
Number 98976, corresponding linked list: 9->8->9->7->6->null
Number 198,   corresponding linked list: 1->9->8->null

The output returned by the program for above two linked lists as input should be the linked list 9->9->1->7->4->null


Video coming soon!



Subscribe for more updates


Algorithm/Insights

Because we are not allowed to use extra space explicitly, we will be making use of recursion to solve this problem.

Corresponding nodes: First let us define corresponding nodes before diving into the algorithm. If we are to add the linked list 9->8->9->7->6->null with the linked list 1->9->8->null then corresponding nodes are those vertically aligned nodes when the linked lists are placed against each other in the right aligned manner. For above linked lists,
9->8->9->7->6->null
      1->9->8->null
as can be observed, last node '6' of the first list and the last node '8' of the second list are corresponding nodes. Similarly, pairs of node '7' and node '9', node '9' and node '1' are corresponding nodes. Now for the first and second nodes of the first list(node '9' and node '8'), there are no corresponding nodes. In such a case, we use 'null' nodes as the corresponding nodes.

Recursive algorithm: If the function addLists(ListNode node1, ListNode node2) adds two lists starting from 'node1' and 'node2' where 'node1' and 'node2' are corresponding nodes as defined above, then
1. We first find out the linked list and the carry obtained by adding the lists after 'node1' and 'node2'. We find this list and carry by making a recursive call addLists(node1.next, node2.next). Let the list returned by this recursive call be 'tempList' and let the carry returned be 'tempCarry'.
2. Once we have this 'tempList' and 'tempCarry', we make a new list node with value as - (node1's value + node2's value + tempcarry)%10 and append the 'tempList' to this new node. This would result in a new linked list which we will return from this current function call. We also return the value of carry from this function which is obtained by using (node1's value + node2's value + tempcarry)/10.
3. Finally when the very first call to addLists(ListNode node1, ListNode node2) is returned, we check if it has returned a carry greater than 0. If the carry returned is not greater than 0 then the list returned by this first call to addLists(ListNode node1, ListNode node2) is the answer. But if the carry returned is greater than 0 then we create a new node with value as the returned carry and append the resultant list returned by the first function call addLists(ListNode node1, ListNode node2) to this newly created node. The resulting new list is the answer in this case.

Handling lists of different lengths: Note that above recursive algorithm assumes that in function addLists(ListNode node1, ListNode node2), 'node1' and 'node2' are corresponding nodes. If the lengths of the lists are different then care must be taken to make sure that 'null' nodes are passed as the corresponding nodes for the extra nodes remaining after right-aligning the given two lists. And value of the 'null' node used is 0 when calculating sum and carry. For example, for the following lists -
9->8->9->7->6->null
      1->9->8->null
for the first two nodes of the first list(node '9' and node '8'), corresponding nodes from the second list would be 'null'.

Java implementation details: In the above recursive algorithm, we are assuming that the function addLists(ListNode node1, ListNode node2) returns link list and carry obtained by adding lists starting from 'node1' and 'node2'. But Java does not allow two objects to be returned. As a work around for this limitation, we pass int array carry[] in the function as an argument and modify carry[0] in each function call which will be then used by the calling function.

The logical flow of the recursive calls for adding lists 9->8->9->7->6->null and 1->9->8->null is shown below:


Please check out code snippet below for implementation details. It has additional comments for more details.


Algorithm Visualization




Code Snippet

			
package com.ideserve.nilesh.questions;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Add two numbers represented by linked lists using recursion.
 * @author Nilesh
 */
public class AddNumbersLinkedList 
{
    private class ListNode
    {
        int value;
        ListNode next;

        ListNode(int value)
        {
            this.value = value;
        }
    }
    
    ListNode head;
    ListNode tail;
    
    // appends node at the end of the list
    private void appendNode(int value)
    {
        if (head == null)
        {
            head = new ListNode(value);
            tail = head;
            return;
        }
        
        ListNode n = new ListNode(value);
        tail.next = n;
        tail = n;
    }

    // creates and returns a new list with node values taken from number[] array
    public ListNode createLinkedList(int[] number)
    {
        // if the head is pointing to some existing list, make it null
        // let the clients handle and store the reference to head
        if (head != null)
        {
            head = null;
        }
        
        for (int i = 0; i < number.length; i++)
        {
            appendNode(number[i]);
        }
        return head;
    }
    
    public void printList(ListNode head)
    {
        ListNode temp = head;
        
        while (temp != null)
        {
            System.out.print(temp.value + "->");
            temp = temp.next;
        }
        System.out.print("null");
    }
    
    private int countDiff(ListNode head1, ListNode head2)
    {
        int extraNodes = 0;
        
        ListNode temp = head1;
        while (temp != null)
        {
            extraNodes += 1;
            temp = temp.next;
        }
        
        temp = head2;
        while (temp != null)
        {
            extraNodes -= 1;
            temp = temp.next;
        }

        return extraNodes;
    }
    
    /*
     * Adds the two lists(which represent numbers) starting from node1 and node2-
     * and returns reference to the first node of the resultant list along with generated carry. 
     * extraNodes > 0, indicates that the length of list1 is greater than length of the list2
     * extraNodes > 0, indicates that the length of list2 is greater than length of the list1
     * extraNodes = 0, indicates lists of equal length.
     *  
     * References for head1 and head2 are used to start adding a list from the beginning if the earlier nodes    
     * passed were null.
     */
    private ListNode addLists(ListNode node1, ListNode node2, int extraNodes, int[] carry, ListNode head1, ListNode head2)
    {
        // if both lists are null, both sum and carry are 0. 
        // we don't need to create a new linked list in this case  
        if (node1 == null && node2 == null)
        {
            carry[0] = 0;
            return null;
        }
        ListNode nextNode;
        
        if (extraNodes > 0) // list1 has extra nodes hence pass corresponding node as null node from list2
        {
            nextNode = addLists(node1.next, null, extraNodes-1, carry, head1, head2);
        }
        else if (extraNodes < 0) // list2 has extra nodes hence pass corresponding node as null node from list1
        {
            nextNode = addLists(null, node2.next, extraNodes+1, carry, head1, head2);
        }
        /*
         * If null nodes were being passed earlier(node1 == null or node2 == null) for any of the lists then that must have been because 
         * of the length difference of the lists.
         * If now the lengths have become equal, corresponding node passed of the shorter lists must be  
         * the head node of the list for the first time when lengths became equal.
         * 
         * If node1 and node2 both are non-null, then we are looking at lists of equal length and we need to simply pass 
         * the next nodes for addition. 
         */
        else 
        {
            ListNode node1Next = (node1 == null)? head1 : node1.next;
            ListNode node2Next = (node2 == null)? head2 : node2.next;
            
            nextNode = addLists(node1Next, node2Next, 0, carry, head1, head2);
        }
        
        // if a node is null then we consider its value as 0
        int value1 = (node1 != null) ? node1.value : 0;
        int value2 = (node2 != null) ? node2.value : 0;
        
        // create a new node with value as 'sum' and update the carry for the calling function 
        int sum  = (value1 + value2 + carry[0]) % 10;
        carry[0] = (value1 + value2 + carry[0]) / 10;
        
        ListNode currentNode =  new ListNode(sum);
        currentNode.next = nextNode;
        
        return currentNode;
    }
    
    public ListNode addLists(ListNode head1, ListNode head2)
    {
        if (head1 == null)
        {
            return head2;
        }
        else if (head2 == null)
        {
            return head1;
        }
        
        int[] carry = new int[1];
        
        ListNode result;
        /* 
         * Count the differences of number of nodes. For equal length lists, difference would be 0.
         * If list1 is longer, difference would be positive, if list2 is longer difference would be negative
         */
        int extraNodes = countDiff(head1, head2);
        
        if (extraNodes > 0)
        {
            /*
             * If list1 is longer, list2 node corresponding to first node of list1 would be null.
             * Difference in the length of the lists would be reduced by 1
             */
            result = addLists(head1, null, extraNodes - 1, carry, head1, head2);
        }
        else if (extraNodes < 0)
        {
            /*
             * If list2 is longer, list1 node corresponding to first node of list2 would be null.
             * Difference in the length of the lists would be reduced by 1.
             * Since difference is negative in this case, we add 1 to get it closer to 0
             */
            result = addLists(null, head2, extraNodes + 1, carry, head1, head2);
        }
        else
        {
            // if the lengths are equal, we simply pass the first nodes of both lists
            result = addLists(head1, head2, 0, carry, head1, head2);
        }
        
        /*
         * After the lists are added, if there is any carry remaining,
         * we need to create a new node with its value as 'carry'.
         * This new node would be the first node if the resultant list 
         */
        if (carry[0] != 0)
        {
            ListNode tempNode = new ListNode(carry[0]);
            tempNode.next = result;
            result = tempNode;
        }
        return result;
    }
    
    
    public static void main(String[] args) 
    {
        AddNumbersLinkedList solution = new AddNumbersLinkedList();

        int[] firstNumber  = {9,8,9,7,6}; // number: 98976
        int[] secondNumber = {1,9,8}; // number: 198
        
        // 9->8->9->7->6->null
        ListNode head1 = solution.createLinkedList(firstNumber);
        
        // 1->9->8->null
        ListNode head2 = solution.createLinkedList(secondNumber);
        
        ListNode result = solution.addLists(head2, head1);
        
        System.out.print("Resultant sum represented as a linked list is: \n");
        solution.printList(result);
    }
}
		

Order of the Algorithm

Time Complexity is O(n)


Contribution

  • Sincere thanks from IDeserve community to Nilesh More for compiling current post.

    Nilesh More

    Ninja Programmer