Sum of Two Linked Lists using Stacks

Given two numbers which are represented using linked lists as shown below. Your program should return the reference to a new linked list which stores the sum of given two numbers.

Numbers are represented as following:
Number 99971, corresponding linked list: 9->9->9->7->1
Number 998,   corresponding linked list: 9->9->8

The output returned by the program for above two linked lists as the input should be the linked list 1->0->0->9->6->9 which represents number 100969 which is sum of numbers 99971 and 998.


Video coming soon!



Subscribe for more updates


Preparing for interviews? IDeserve team is here to help.




Algorithm/Insights

We have discussed recursive algorithm to solve this problem in this previous post. In this post we will be discussing a non-recursive algorithm to add two numbers represented using linked lists.

Idea: Because the unit digits of numbers are placed at the end of the linked lists which represent them, to add given two numbers, we need to start adding the values of the nodes starting from the end nodes of linked lists. For example, to add numbers 99,171(9->9->9->7->1) and 998(9->9->8), we start by adding node with value '1' of the first list to the node with value '8' of the second list. To enforce this reverse ordering, we can push the given two lists to two different stacks thereby placing the unit digits at the top of the stacks and then starting the addition process by popping digits from the stacks one by one. Also since we need to return the resultant number represented in the form of a linked list(which has unit digit at the end), we push the addition result onto a stack and create the linked list out of this stack. For adding two numbers 99,171 and 998, the stacks will look like following after pushing the two linked lists to stacks.
        
And the result of addition of these two numbers would again be pushed to stack digit by digit. This resultant stack then would be converted to the linked list.


Algorithm: The formal steps of this algorithm are as following:
1. Create stack 's1' by pushing all node values of the first linked list to a stack.
2. Create stack 's2' by pushing all node values of the second linked list to a stack.
3. Create an empty stack 's3' to store the result of addition.
4. Initialize sum and carry to 0.
5. Pop the top element from stack 's1'. Let this top element be 'value1'.
6. Pop the top element from stack 's2'. Let this top element be 'value2'.
7. Make 'sum' = (value1 + value2 + carry)%10 and push this 'sum' to stack 's3' and make 'carry' = (value1 + value2 + carry)/10.
8. Repeat steps 5-7 till one of the stacks become empty. If both stacks are of same size, then both of the stacks would become empty at the same time.
9. If stack 's1' has elements left in it then -
    a. Pop the top element from stack 's1'. Let this top element be 'value1'.
    b. Make 'sum' = (value1 + carry)%10 and push this 'sum' to stack 's3' and make 'carry' = (value1 + carry)/10.
    c. Repeat steps 9a and 9b until stack 's1' is not empty.
10. Similarly, if stack 's2' has elements left in it then -
    a. Pop the top element from stack 's2'. Let this top element be 'value2'.
    b. Make 'sum' = (value2 + carry)%10 and push this 'sum' to stack 's3' and make 'carry' = (value2 + carry)/10.
    c. Repeat steps 10a and 10b until stack 's2' is not empty.
11. After all the above steps are executed, if carry is greater than 0, push it to the resultant stack 's3'.
12. Create an empty linked list 'result'. Now pop elements one by one from the stack 's3', and keep appending them to the 'result' linked list until stack 's3' is not empty. Return the output as 'result' linked list.  
    
Please check out the function 'addLists(ListNode node1, ListNode node2)' from code snippet below for implementation details. The time and space complexity of this approach is O(n).


Hone your coding skills!




AngryNerds Practice platform »

Algorithm Visualization




Code Snippet

			
package com.ideserve.nilesh.questions;

import java.util.Stack;

/**
 * <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 by making use of stacks.
 * @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 the stack 's'
    private ListNode createLinkedList(Stack<Integer> s)
    {
        // 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;
        }
        
        while (!s.isEmpty())
        {
            appendNode(s.pop());
        }
        return head;
    }
    
    // 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");
    }
    
    
    public ListNode addLists(ListNode node1, ListNode node2)
    {
        if (node1 == null)
        {
            return node2;
        }
        if (node2 == null)
        {
            return node1;
        }
        
        Stack<Integer> s1 = new Stack<Integer>();
        Stack<Integer> s2 = new Stack<Integer>();
        Stack<Integer> s3 = new Stack<Integer>();
        
        // push list1 into the first stack
        ListNode temp = node1;
        while (temp != null)
        {
            s1.push(temp.value);
            temp = temp.next;
        }
        
        // push list2 into the second stack
        temp = node2;
        while (temp != null)
        {
            s2.push(temp.value);
            temp = temp.next;
        }

        int sum = 0, carry = 0, value1, value2;
        
        // keep adding the popped digits to the sum until one of the stacks becomes empty
        // sum itself is stored in a stack
        while ((!s1.empty()) && (!s2.empty()))
        {
            value1 = s1.pop();
            value2 = s2.pop();
            
            sum   = (value1 + value2 + carry) % 10;
            carry = (value1 + value2 + carry) / 10;
            
            s3.push(sum);
        }
        
        // if stack1 still has some digits left, add those digits to the sum 
        while (!s1.isEmpty())
        {
            value1 = s1.pop();
            
            sum   = (value1 + carry) % 10;
            carry = (value1 + carry) / 10;
            
            s3.push(sum);
        }
        
        // if stack2 still has some digits left, add those digits to the sum
        while (!s2.isEmpty())
        {
            value2 = s2.pop();
            
            sum   = (value2 + carry) % 10;
            carry = (value2 + carry) / 10;
            
            s3.push(sum);
        }
        
        // after adding digits from both the stack, if the remaining carry is greater than 0
        // add that carry to the sum
        if (carry > 0)
        {
            s3.push(carry);
        }
        
        // finally, from the resultant stack, which stores the sum create a new linked list
        // return this newly created linked list
        return createLinkedList(s3);
    }
    
    
    public static void main(String[] args) 
    {
        AddNumbersLinkedList solution = new AddNumbersLinkedList();

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

Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(n)


Contribution

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

    Nilesh More

    Ninja Programmer