Add Two Numbers Represented by the Linked Lists | Part-2

Approach Using Stacks

In this approach, we will use stacks to add the numbers formed by linked lists. We are using the stack for this problem to get a better time complexity than part 1 of this problem.

We will create three stacks for this problem. Stack 1 stores the elements from linked list 1, stack 2 stores linked list 2, and stack 3 stores the sum of the elements.

After storing the elements in the stack, we add the top of stack1 and stack2 and store it in a sum variable, and then we will store that sum variable into a node and push the node in stack3. We will repeat this process until both stacks are empty.

If the size of the stacks is not equal, we will apply different conditions for each and perform the addition.

If there is a carry, we will take a counter of it and add it further in addition. We will keep track of the head address of the resultant linked list and return it to the main function. 

Algorithm

1. Take the user input for both linked lists.
    
2. Create three stacks to store the nodes of the linked lists and the resultant linked list.
    
3. Push the linked lists' nodes into the corresponding stacks.
    
4. Add the top elements of the stacks along with carry and push it into the resultant stack.
    
5. Repeat the above step until one of the stacks get empty, or both stacks get empty.
    
6. If one stack gets empty, add the carry to the next node in the other stack and push its remaining nodes into the resultant stack.
    
7. If the carry after pushing the last node is 1, add an extra node with value one into the linked list, 
    
8. Form a linked list of the nodes in the resultant stack and print it.

DRY Run

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

// Structure for a node.
struct node{
	int data;
	struct node * next;
};

// For creating a new node for a number.
node* createnode(int value){
	node *newnode = new node();
	newnode->data = value;
	newnode->next = nullptr;
	return newnode;
}

// Function to add the linked lists.
node* addlists(struct node *head1, struct node *head2){
	/*
	    Node, which will be head of the resultant 
	    linked list and returned
	    to the driver function
	*/
	node *sumhead = nullptr;
	node *list1 = head1;
	node *list2 = head2;

	/*
	    Creating three stacks to store both 
	    the lists to be added and the
	    resultant linked list.
	*/
	stack<node*> stack1, stack2, sumstack;

	/*
	    Pushing the nodes from the 
	    first linked list into the stack.
	*/
	while (list1 != nullptr){
		stack1.push(list1);
		list1 = list1->next;
	}

	/*
	    Pushing the nodes from the 
	    second linked list into the stack.
	*/
	while (list2 != nullptr){
		stack2.push(list2);
		list2 = list2->next;
	}

	int carry = 0;

	/*
	    Add the nodes of both the linked list, along with the carry
	      from the addition of the previous nodes. 
	    Store the sum in the stack for the resultant linked list.
	*/
	while (!stack1.empty() || !stack2.empty()){
		int sum = (!stack1.empty() ? stack1.top()->data : 0) + (!stack2.empty() ? stack2.top()->data : 0) + carry;
		node *sumnode = createnode(sum % 10);

		sumstack.push(sumnode);

		carry = sum / 10;

		if (!stack1.empty()){
			stack1.pop();
		}

		if (!stack2.empty()){
			stack2.pop();
		}
	}

	if (carry != 0){
		node *extranode = createnode(carry);
		sumstack.push(extranode);
	}

	/*
	    Forming the resultant linked
	    list from the nodes in the stack.
	*/
	if (!sumstack.empty()){
		sumhead = sumstack.top();
	}

	while (!sumstack.empty()){
		node *curr = sumstack.top();
		sumstack.pop();
		if (sumstack.size() == 0){
			curr->next = NULL;
		}
		else{
			curr->next = sumstack.top();
		}
	}

	/*
	    Returning the head of
	    the resultant linked list.
	*/
	return sumhead;
}

// Function to push nodes into the list.
void push(struct node **headr, int newval)
{
	// Creating a new node.
	struct node *newnode = createnode(newval);

	// For empty linked lists.
	if (*headr == nullptr){
		newnode->next = *headr;
		*headr = newnode;
		return;
	}

	// Pushing the node in the linked list.
	node *temp = *headr;
	while (temp->next != nullptr && temp != nullptr){
		temp = temp->next;
	}

	temp->next = newnode;
	return;
}

// Driver function.
int main()
{
	node *head1 = nullptr;
	node *head2 = nullptr;
	
	// Linkedlist1 elements
	push(&head1,3);
	push(&head1,8);
	push(&head1,1);
	push(&head1,3);
	push(&head1,5);
	
	// Linkedlist2 elements
	push(&head2,6);
	push(&head2,2);
	push(&head2,4);
	push(&head2,3);
	push(&head2,5);

	// Calling the addition function.
	struct node *sumlist = addlists(head1, head2);

	// Printing the final linked list.
	cout << "Resultant Linked List: ";
	while (sumlist != nullptr){
		cout << sumlist->data << " ";
		sumlist = sumlist->next;
	}

	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input

Linked list1: 3 8 1 3 5

Linked list2:  6 2 4 3 5

Output

Implementation in Python

# Creating the node
class Node:
    def __init__(self,data):
        self.data = data
        self.nextAddress = None


# Creating the linked lists of nodes
class Createlinkedlist:
    def __init__(self):
        self.head = None
        self.last = None
    
    def pushdata(self,data):
        if self.head == None:
            self.head = Node(data)
            self.last = self.head
        else:
            self.last.nextAddress = Node(data)
            self.last = self.last.nextAddress


# Performing the addition of linked lists
class AddLinkedLists:
    def __init__(self):
        self.head = None
    
    def addnumbers(self,list1,list2):
        stack1 = []
        stack2 = []
        stack3 = []
        carry = 0
        output = None
        
        # Adding elements of linkedlist1 in stack1
        while list1!=None:
            stack1.append(list1.data)
            list1 = list1.nextAddress
            
        # Adding elements of linkedlist2 in stack2
        while list2!=None:
            stack2.append(list2.data)
            list2 = list2.nextAddress
            
        # Performing addition unitl stack1 and stack2 is empty.
        # Pushing the result in stack3.
        while(stack1 and stack2):
            output = stack1.pop() + stack2.pop() + carry
            
            carry = int(output/10)
            
            output = output if output<10 else output%10
            stack3.append(output)
        # If stack1 or stack2 is not empty adding 
        # the remaining elements in stack3.
        while stack1:
                output = carry + stack1.pop()
                carry = int(output/10)
                output = output if output<10 else output%10
                stack3.append(output)
                
        while stack2:
                output = carry + stack2.pop()
                carry = int(output/10)
                output = output if output<10 else output%10
                stack3.append(output)
    
        if carry!=0:
            stack3.append(carry)
        
        for i in range(len(stack3)):
            resultant = Node(stack3[i])
            if self.head == None:
                head = resultant
            else:
                resultant.nextAddress = self.head
            self.head = resultant
        return self.head
        
# Printing the linked lists
def printlinkedlist(head):
    while head:
        print(head.data,end=' ')
        head = head.nextAddress
    
    print()

# Driver function
if __name__ == '__main__':
    
    # Linkedlist1 elements
    obj1 = Createlinkedlist()
    obj1.pushdata(3)
    obj1.pushdata(8)
    obj1.pushdata(1)
    obj1.pushdata(3)
    obj1.pushdata(5)
    
    # Linkedlist2 elements
    obj2 = Createlinkedlist()
    obj2.pushdata(6)
    obj2.pushdata(2)
    obj2.pushdata(4)
    obj2.pushdata(3)
    obj2.pushdata(5)
    
    obj3 = AddLinkedLists()
    resultant = obj3.addnumbers(obj1.head,obj2.head)
    print("resultant linkedlist: ")
    printlinkedlist(resultant)

You can also try this code with Online Python Compiler

Run Code

Input

Linked list1: 3 8 1 3 5

Linked list2:  6 2 4 3 5 

Output

Complexity Analysis

The time complexity for this approach is - O(M+N) here, M is the size of the first linked list, and N is the size of the second linked list.

The space complexity for this approach will be - O(M+N), where M is the size of stack1 and N is the size of stack2.

Also check out Addition of Two Numbers in Java here.

Frequently Asked Questions

What is the top() function in stacks?

The top() function returns the last inserted element in a stack.

How can we insert an element into a stack?

We can insert an element into the stack using the following syntax- <name of the stack>.push(<the value to be inserted>) .

How can we form a linked list from a stack containing nodes of another linked list?

We can pop the nodes from the stack and set their next pointer to the previously popped node. Then, set the last node as the head of the linked list, and the node's next pointer was removed first to null.

What is a carry variable in the above method?

If the sum of two digits of a number is greater than 9, we use the carry variable to store the second digit of the full, which is later added to the next digit of the sum.

Is it possible to implement a stack using a linked list?

Yes, it is possible to implement a stack using a linked list only if we restrict adding and removing operations of the nodes into the linked list to one of its ends.

Conclusion

In this blog, we discussed using stacks to add two numbers represented by the linked lists. We have discussed why we are using the stack approach for this problem. We have addressed the time and space complexity for implementation.

Recommended Reading:

• Add Two Numbers Represented by Linked Lists | Part 3
• Add two numbers represented by the linked lists | Part 1
• Application of Linked Lists
• Design Browser History
• Union and Intersection of two Linked Lists
• Rotate a Linked List
• Subtract Two Numbers represented as Linked Lists
• Advantages and Disadvantages of Linked List
   

Do check out the Interview guide for Product Based Companies as well as some of the popular interview problems from top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, and System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Coding!