MCN Professionals | Interview Question of the day
MCN Professionals is starting Industrial Training for MCA-2012 Batch. Have a look at our Industrial Training Program and Course Details.
-----------------------------------------------------------------------------------------------------------------------------------------
Today's Question:
Two numbers are given in the form of linked list (with each node storing one digit), like below:
Number1: 1 -> 2 -> 4 (Number: 124)
Number2: 1 -> 0 -> 2 -> 3 -> 4 (Number: 10234)
Write an algorithm which will compute the sum of these two linked list. The result should be a linked list as below:
Sum: 1 -> 0 -> 3 -> 5 -> 8 (Number: 10358)
Solution:
The problem is because during addition, we add from the least significant bits:
There are multiple solutions to solve this problem:
Method1: Reverse the lists
Algorithm:
Step1: Reverse list1
Step2: Reverse list2
Step3: add list1 & list2 from forward direction and keep adding the new element at the front of result list.
For example:
If the original lists are
Num1: 1 -> 2 -> 4
Num2: 1 -> 0 -> 2 -> 3 -> 4
Reversing the lists
Num1: 4 -> 2 -> 1
Num2: 4 -> 3 -> 2 -> 0 -> 1
Adding the lists
Num1: 4 -> 2 -> 1
Num2: 4 -> 3 -> 2 -> 0 -> 1
Sum: 8 -> 5 -> 3 -> 0 -> 1
Reverse the Sum list to get the actual sum:
Sum: 1 -> 0 -> 3 -> 5 -> 8
Note that we don't need the last step if we keep inserting at the head of the list in the previous step.
Node* computeSum(Node* num1, Node* num2)
{
// If any of the list is null return the other list
if(!num1)
return num2;
else if(!num2)
return num1;
// Reversing the two list
reverse(num1);
Node * sum = NULL;
Node * temp = NULL;
int carry = 0; // variable to hold carry of sum.
while(num1 && num2)
{
int tempSum = (carry + num1->data + num2->data) % 10;
carry = (carry + num1->data + num2->data) / 10;
if(! sum){
temp = sum = new Node(tempSum); // sum will point to the head of result list
}else{
temp->link = new Node(tempSum);
temp = temp->link;
}
}
// Adding the remaining list to the end of result list
if(num1)
temp->link = num1;
else
temp->link = num2;
// Reversing the result list
reverse(sum);
return sum;
}
Method 2: using Stacks
This algorithm does not require us to reverse the list. Following are the steps:
Algorithm:
Step1: Push all the nodes of num1 in Stack1
Step2: Push all the nodes of num2 in Stack2
Step3: Keep popping the elements from two stacks and adding them and inserting them in the result list.
---------------------------------------------------------------------------
Interview Questions Archive:
To see all the questions in the category click
here...