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 theselinked 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

Take the user input for both linked lists.

Create three stacks to store the nodes of the linked lists and the resultant linked list.

Push the linked lists' nodes into the corresponding stacks.

Add the top elements of the stacks along with carry and push it into the resultant stack.

Repeat the above step until one of the stacks get empty, or both stacks get empty.

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.

If the carry after pushing the last node is 1, add an extra node with value one into the linked list,

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;
}

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)

Input

Linked list1: 3 8 1 3 5

Linked list2: 6 2 4 3 5

Output

Complexity Analysis

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

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

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.