Hey coder. Let's start with the question, "Add Two Linked Lists". We suggest you watch the question video first.
Important Links : Question Video, Solution Video
Prev Next
Add Two Linked List
None of us really changes over time. We only become more fully what we are.
~Anne Rice
Add Two Linked List
Problem Discussion :
- You are required to write a function which is passed two linked lists and represents two numbers - the first element is the most significant digit and the last element is the least significant digit.
- The function is expected to add the two linked lists and return a new linked list.
DON'TS
- Don't reverse the linked lists in order to access them from least significant digit to most significant.
- Don't use arrays or explicit extra memory.
- Don't convert linked lists to numbers, add them up and convert the result back to a linked list.
CONSTRAINTS
- Time complexity = O(n)
- Space complexity = Recursion space, O(n)
This question is to be solved using the same trick we used in the previous questions, "Fold a linked list", "Is linked List a palindrome?" and "Display Reverse- Recursive".
Approach :
To solve this problem we will use a recursive approach.
The idea here is that we need to add the list but as we know that addition is only possible when traversing from the end like adding firstly the unit place elements and then carry forwarding to the next place and so on.
This generalized process here we will try to implement using recursion as we are not allowed to reverse the list.
Let's see the solution through an example.
We take the linked lists as 9-8-7-5 and 4-6. On top of each digit the place value of that digit is written in white.
We use stack to understand this problem. It is divided into 2 parts: Going up the stack and Going down the stack.
UP THE STACK(PUSH)
We make a stack and add the most significant digits of both the linked lists along with their place values (digits are denoted in white and place value in red in the figure 3).
Since the place values of "one" and "two" are different they can't be added together. Hence we move towards the lesser significant digits for "one" till the place value of "one" and "two" is the same.
We reach the position shown in figure 4 where the place values are the same.
But we don't start the addition now because we have to start from the least significant digit and move towards the most significant digit.
We move both the pointers forward and push a new level in the stack until they reach null (see figure 5).
We reach the end of our pushing process.
DOWN THE STACK (POP)
Now when we have reached the null position, we are going to return 0 as the carry value. This is our Base Condition.
Now we take the sum of carry and the two digits. Here, the new carry is the ten's digit of the sum. This new carry is returned.
Also, the one's digit of the sum is added first to the resultant linked list.
In our example, 0+5+6=11. Hence ten's digit 1, the new carry is returned and one's digit, 1 is added to the resultant as shown in figure 7.
As 1 is returned to the digits at place value 2, the process is repeated. Our sum =1+7+4=12. Now 1 is the new carry and 2 is added first to the resultant linked list.
As all the digits of the second linked list have been used up, therefore we just include carry and the next digit of the first linked list. So, 1+8=9. Hence, new carry is 0 and 9 is added first to the resultant.
Again, for the greatest significant digit, 0+9=9 is the sum. Hence 0 is returned as carry and 9 is added first.
*Had the carry been more than 0 we would have added that value of carry in the resultant linked list too.
Our final answer hence looks like as shown in figure 9.
Hence our answer is 9921.
Try to write the code for the above explanation yourself. If you face any problems, feel free to refer to the code given below.
private static int addhelper(Node one,int pv1, Node two,int pv2,LinkedList res){ if(one==null && two==null){
return 0;
}
int sum=0;
if(pv1>pv2){
int oc=addhelper(one.next,pv1-1,two,pv2,res); //pv1=place value of 1
sum=one.data+oc;
}
else if(pv2>pv1){
int oc=addhelper(one,pv1,two.next,pv2-1,res); //pv2=place value of 2
sum=two.data+oc;
}
else{
int oc=addhelper(one.next,pv1-1,two.next,pv2-1,res); //oc= old carry
sum=one.data+two.data+oc;
}
int c=sum/10; //new carry
int d=sum%10; //new digit of "res"
res.addFirst(d);
return c;
}
public static LinkedList addTwoLists(LinkedList one, LinkedList two) {
LinkedList res=new LinkedList();
int oc=addhelper(one.head,one.size, two.head,two.size, res);
if(oc>0){
res.addFirst(oc);
}
return res;
}
java;
true";
We highly suggest you watch the solution video for this problem, to see it dry run multiple times.
Analysis:
Time Complexity:
O(n)
Since recursion calls are made in this program, therefore its complexity is linear.
Space Complexity:
O(n)
The recursion space used in this program is of order n hence the space complexity is linear.
