Welcome back.
Let's now think how we can solve this question.
Now to start with, let's just walk through an addition of two numbers.
Let's say we want to add 628 and 567.
Now how would we do it normally first we would add eight and seven and we get 15.
So we write five over here and one is going to be carry forward.
Now we add one two and six.
And that's going to be equal to nine.
And then we add six and five.
So that's equal to 11.
So we write one over here and one over here.
So this is actually a carry forward this one over here.
But because there is nothing over here.
So we just write this one over here.
So that is how we have the normal addition right.
So everyone is aware of this.
Now let's try to think how we can implement this in our code.
And we are using the linked list.
So we have these two linked lists.
We have eight pointing to two pointing to six.
And then we have seven pointing to six pointing to five.
Now over here you can see that we actually start adding from the units digit over here.
So it's actually in our advantage that the linked lists are in the reverse order.
Now what can we do over here.
We have to add these two.
So what we do is first let's take these two values.
So that's the head of the two linked list.
So we get eight over here and seven over here.
Now let's add them.
So we get eight plus seven.
That's equal to 15.
Now let's we over here we have seen that we actually want only the unit digit over here.
Right.
So to get this what we can do is we will take this 15 and then we will do percentage ten or modulo ten.
So that will give us the remainder when 15 is divided by ten which is actually this digit over here.
So by doing this we will get the value five.
Now let's take this five and make a node.
And we make it the head of the output linked list.
So we have five over here.
Now we also need to check whether there is any carry forward.
Now how do we do that.
So for that let's take this 15.
And let's divide this by ten and floor it like for example if you take this 15 and we divide it by ten
we will get 1.5.
Now if we floor this or round it down right, this will become equal to one which is actually this number
over here.
And that is what will be carry forward.
Right.
So we can do floor of 15 divided by ten which is equal to one.
And that is the carry forward.
All right.
So let's make a note of the carry forward.
So we will just write it over here.
So we have one over here which is the carry forward.
Now let's proceed.
So we are done with these two nodes.
So we are going to move ahead in both these linked lists.
So over here we get two.
And then over here we get six.
Again we take these two values and we add them.
And then we add the carry forward also along with this.
So two plus six plus one gives us nine.
Right.
So that's equal to nine.
Now we take this nine.
And then we are going to take percentage ten or modulo ten on it.
So that's the remainder when nine is divided by ten.
So that gives us nine itself.
So we take this value and we are going to make a node out of it.
And this is made to point to the next node.
All right.
And then we have to check whether there is a carry forward or not.
Now we know that there is no carry forward over here, but in the code to check whether there is a carry
forward or not.
All that we need to do is we need to divide nine by ten and then floor it.
This is the same thing that we did previously.
So when we divide nine by ten we will get 0.9.
And when we floor it that becomes zero which means that the carry forward is equal to zero.
All right.
So we have got these two nodes.
Let's proceed.
So we are going to move ahead in these two linked lists which is given to us.
So over here we have six.
And over here we have five.
Again let's go ahead and add these two.
And there is no carry forward.
So six plus five is equal to 11.
Now let's try to learn or understand what value to take over here.
When we make a node for this we are going to take this 11.
And again we will do percentage ten or modulo ten.
And that gives us the remainder when 11 is divided by ten which is equal to one.
So we are going to take this value one over here.
And then we will make a node with this value.
And then we will make nine point to this.
All right.
Now let's check whether there is a carry forward over here.
For this we take this 11.
And let's just divide it by ten and floor it.
So if we do this when we do 11 by ten we will get 1.1.
And when we floor it we will get one which is this value over here.
Right.
And we can see that's the carry forward.
All right.
So there is a carry forward of one.
So let's just make a note of it over here.
All right.
So we have one over here.
And then we are going to move forward.
Now when we move forward we see that in these two linked lists right.
We have null.
We have null and null over here.
So when we add whatever values are there over here there is just this carry forward over here which
is equal to one.
Now again let's take one percentage ten one modulo ten.
That gives us one.
So we take this value one.
And we make a node out of it.
And we make this one point to this node over here.
Again we are going to check if there is a carry forward.
For this.
We will do one divided by ten.
And then we are flooring it.
And that gives us zero right.
One by ten is 0.1.
And when we floor it we will get zero which means that there is no carry forward and hence we can stop.
So this is how we can solve this question.
And the interesting thing that you have to notice over here is we have to keep iterating through the
linked list, as long as there is an element in either of the linked lists, or if there is something
in the carry forward.
So that is the that is very important.
Alright, so even if there is no node in both the linked list, still, if there is a carry forward
we need to keep iterating because still over here you can see we have to make one more node.
So this is something very important which you should not miss.
All right.
So this is how we will solve this question.
Now let's take a quick look at the space and time complexity of this solution.
Now let's first look at the time complexity.
What would be the number of operations that we have to do now over here we have seen that we had to
go through the linked list.
Right.
We have to traverse the linked list.
So let's say both the linked lists are of different length.
It could be that we have one linked list which has let's say four elements and one linked list which
has just two elements.
Now in this case we would have to go through the longer one.
Right.
So we can say that the time complexity is equal to of the order of the length of the longer linked list.
All right.
So if both of them are the same then it would be the same.
But let's say one is of length m and one is of length n.
Then we can say that the time complexity is of the order of maximum between m and n.
All right.
Now, what about the space complexity?
You can see that we do take up space because we have to return the output as a linked list.
So this is going to take up space right.
So we have to make a new linked list.
Now the size of this linked list.
The new linked list the maximum possible size is going to be the length of the longer linked list plus
one right.
For example, in this case you can see both of these linked lists are of size three and this linked
list over here the output linked list is of size four.
So you can have plus one over here if there is a carry forward.
So this is the maximum possible length of the output linked list.
So we can say that the space complexity is going to be of the order of the length of the longer linked
list, which is the same thing which we got for the time complexity as well.
So again, we can write it in this manner.
Also, space also is going to be of the order of the maximum between M and N.