Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
1.
Introduction
2.
Problem Statement
3.
Approach Using Stacks
3.1.
Algorithm
3.2.
DRY Run
3.3.
Implementation in C++
3.4.
Complexity Analysis
4.
4.1.
What is the top() function in stacks?
4.2.
How can we insert an element into a stack?
4.3.
How can we form a linked list from a stack containing nodes of another linked list?
4.4.
What is a carry variable in the above method?
4.5.
Is it possible to implement a stack using a linked list?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

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

## Introduction

We have discussed this problem statement in PART-1 by adding preceding zeroes. But you must know there can be multiple solutions for a particular problem. In this second part-2, the problem statement will remain the same, but we will apply a different approach.

This blog will discuss a problem statement based on the linked list, a famous problem asked about in many interviews.

## Problem Statement

Let's discuss the problem statement again to brush it up.

Suppose there are two linked lists such that all the nodes of these linked lists contain numbers between 1 and 9. Now we are asked to find the sum of the numbers formed by these linked lists treating nodes as the digits of a number.

To tackle this problem, we will be using the stack approach.

For Example

Input

Numbers of Nodes in linked list 1 and 2: 5 5

Nodes in linked list 1: 3 -> 8 -> 1 -> 3 -> 5

Nodes in linked list 2: 6 -> 2 -> 4 -> 3 -> 5

Output

1 -> 0 -> 0 -> 5 -> 7->0

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## 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.

### 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, 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
*/
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()){
}

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.
*/
}

// 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){
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;

// Calling the addition function.

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

return 0;
}``````

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

# Creating the linked lists of nodes
def __init__(self):
self.last = None

def pushdata(self,data):
if self.head == None:
else:

# Performing the addition of linked lists
def __init__(self):

stack1 = []
stack2 = []
stack3 = []
carry = 0
output = None

# Adding elements of linkedlist1 in stack1
while list1!=None:
stack1.append(list1.data)

# Adding elements of linkedlist2 in stack2
while list2!=None:
stack2.append(list2.data)

# 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:
else:

# Printing the linked lists

print()

# Driver function
if __name__ == '__main__':

obj1.pushdata(3)
obj1.pushdata(8)
obj1.pushdata(1)
obj1.pushdata(3)
obj1.pushdata(5)

obj2.pushdata(6)
obj2.pushdata(2)
obj2.pushdata(4)
obj2.pushdata(3)
obj2.pushdata(5)

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.