Welcome back.
Let's now go ahead and code the solution which we discussed in the previous video.
Now over here I have a class node with which I will make the notes.
All right.
And then we have the class linked list.
And over here I've included the added tail function which we have discussed in the construction video
for the singly linked list.
Now we will use this over here to make two linked lists.
So let's try 540 plus 723 once we have written the function.
So to test our code, once we have written the function over here I have made a linked list n1.
And over here you can see that you have uh zero pointing to four pointing to five because we are adding
at the tail.
And then you have three pointing to two pointing to seven over here.
Now we are going to use these two to test our code.
So let's get started.
So let's write the function over here.
Now we can call this function add two numbers.
Now this function is going to take in the head of the two linked lists.
All right.
So let's just call the head L1 and L2.
Now, once inside the function, first let's have a variable called called carry forward.
So let's say carry forward.
Is initially initialized to zero, so it's equal to zero.
And then we will calculate it later.
So let's carry forward equal to zero.
Now we will have a new linked list.
So let's say const.
And let's call it results is equal to new linked list.
So we are using the linked list class to initialize a results object over here.
Now we are going to have a while loop.
And as we discussed in the video where we discussed the method, we have to keep iterating as long as
there is something in either of the linked list which is given to us, or if the carry forward is not
zero.
So over here we are going to have while l one is true or.
L2 is true.
Or carry forward is true.
All right.
So even if L1 and L2 is pointing to null and there is some carry forward, even then we have to iterate.
So this is the condition for the while loop.
Now inside this we are going to calculate the value of L1 and L2.
That is the value in the node L1 and L2.
So for this let's say let L1 value.
Is equal to.
And then we have a condition if L1 is truthy, if there is a node over there then we'll just take L1
dot value.
Otherwise we will just take it as zero.
Similarly for L2 also let's have a variable L2 value.
Now, if L2 is truthy then we will take the value of L2.
So l2 dot value.
Otherwise we will take it as zero.
All right.
So this is important because we have seen that the linked list can be of different length.
And even there can be a case where L1 and L2 are false.
But there is something in carry forward.
All right.
So we have seen that in the explainer video.
Now let's add these values so we can again have one more variable let's say sum.
And this is going to be equal to.
L1 value.
Plus L2 value.
Plus carry forward.
All right.
And this is this is the sum.
And then we want to know what value we should have in the node.
Right.
So let's say let's have a variable for that.
So we could do it here itself.
But let's just make it more readable.
So let's say let.
Node.
Value.
In result.
Be equal to some percentage ten.
So we are dividing it by ten and taking the remainder.
So this is going to be the value of the node in the results array.
Now we just have to add this at the tail to the results linked list.
So we can say results dot add a tail.
And then we are going to pass in the value over here, which is node value in result.
All right.
So so that is it.
So now we also need to check if there is a carry forward.
So let's say carry forward is equal to math dot floor.
And we are taking the sum.
All right.
So we are taking the sum which is uh sum.
And then we divide this by ten.
So this will give us if there is any carry forward.
All right.
And once we are done with this, we just have to move forward in the two linked lists.
So again, you we cannot simply say L1 dot next because we don't know whether it's null.
Right.
Because over here the condition is if L1 is L1 or L2 or carry forward is truthy, we come inside.
So again we have to check if L1 is truthy.
So we can say L1 is equal to.
And if L1 is truthy then we will say L1 dot next.
Otherwise we will just say null.
All right.
Similarly for L2 also L2 is equal to.
If L2 is truthy, then we will say L2 dot next.
Otherwise null.
And that's it.
So once we're out of this while loop, we will have our results linked list.
And then we just need to return this linked list so we can say return results.
And that is it.
This should work.
So let's go ahead and test our code.
So again we have set up the test case over here.
So we are going to add 745 40 and 723.
So let's use our function.
So we have add two numbers.
And we are going to pass in the head of linked list n1 and n2.
So over here we will pass n1 dot head and n2 dot head.
All right.
Now let's go ahead and call the function and see what we are getting.
So you can see we have the results, which is a linked list with four nodes.
That is correct.
1002 63 has four digits over here.
Now let's open it up.
And again it's reverse right.
So first it should be three.
So yes we have three at the head.
And then three is pointing to six which is correct.
Which is what we have over here.
And six is pointing to two.
That is also correct.
So we have two over here.
And then two is pointing to one which is correct.
So we have one over here and that is pointing to null.
So yes our code is working.
All right.
Now let's just walk through the code with this example over here.
So let me just take a pen for this.
So we have 540 plus 723, and the linked lists are stored in reverse order.
So we have zero pointing to four pointing to five.
And then we have three pointing to two pointing to seven.
So these are the heads of these.
All right.
So let's go ahead and see what's happening over here.
Now we call the add two numbers function.
Now let's go to that part.
So we are inside the function over here.
And we have the heads which is zero and three which is L1 and L2.
Now carry forward is initialized to zero.
And then we make a new linked list which is results.
At this point results is just null.
Now we see that if L1 or L2 or carry forward is truthy, we have to iterate.
And we see that initially L1 is this head right.
This is L1 and this is L2 and both are truthy.
So we come inside the while loop.
Now we we identify L1 value as the value of L1.
Because L1 is truthy that's equal to zero.
And then L2 value is going to be equal to three.
And some is going to be zero plus three plus carry forward and carry forward is equal to zero.
So some now is going to be equal to three.
And then we are going to do three percentage ten right.
So that gives us three itself.
So the node value in the result is going to be three.
And then we are going to create a node and add it at the tail of the results linked list.
So the results linked list is just null over here at this point.
So we're just making a node over here with three.
And this is pointing to null.
And then we are going to calculate carry forward which is math dot floor.
Some is three three by ten is 0.3.
And when we floor it we will get zero itself.
So carry forward is again zero over here.
All right.
Now let's proceed.
And then L1 is moving.
L1 is equal to L1 dot next and L2 is equal to L2 dot next over here.
So L1 comes over here and L2 comes over here.
And then again we come over here and we check.
So we see both of them are truthy.
So we come inside and we find their value as four and two.
And then sum is equal to four plus two which is equal to six.
Now node value in results this is going to be six percentage ten which is six itself.
And then we are going to create a node with value six.
And we are adding it at the tail.
So the tail over here is here right.
So we're going to add it over here.
So we have six over here.
And this is pointed in this direction.
So for this we are using the add a tail function which we have written in the video where we constructed
the linked list singly linked list.
All right.
So this is done again.
We come over here we calculate the carry forward.
So that's going to be six by ten.
And then flooring it which is again equal to zero.
So the carry forward is still equal to zero.
Now L1 and L2 are moved forward.
So we get L1 is equal to L1 dot next which is over here.
And L2 is equal to L2 dot next which is over here.
All right.
Again we come over here.
We see they are truthy.
So we are going to take their values which is five and seven.
And then we add it up and carry forward is zero.
So five plus seven plus zero.
That's equal to 12.
So sum is equal to 12.
Now note value is equal to 12 percentage ten which is equal to two right.
So that's equal to two.
So over here we are going to add at the tail a node with value two.
So the tail is over here.
So we have a node with value two.
And this is going to point over here.
And this is the new tail.
Now carry forward is calculated as 12 which is the sum divided by ten.
That's equal to 1.2.
And then when we flow it we will get that as one.
So one carry forward now is equal to one.
All right.
Again, we check if L1 is truthy.
Yes, it's truthy.
So we are going to do L1 dot next.
And this is anyway pointing to null right.
So over here this is pointing to null.
And this is also pointing to null.
So L1 dot.
Next when we do L1 dot next we get over here.
Similarly L2 dot next is also going to get us over here.
Now when we come to the while loop condition we see that L1 is null.
L2 is also null, but carry forward is equal to one.
So that's why we again come inside over here inside the while loop.
And over here we see that L1 is falsy because it's null right.
So we're going to take L1 value as zero.
And L2 also is falsy.
So L2 value is going to be equal to zero.
That's what we're doing over here.
And then sum is equal to zero plus zero plus one because carry forward is equal to one.
So we're getting the sum as equal to one.
And then node value is equal to one percentage ten.
And that's equal to one itself.
Right.
So we're going to make a node with value one.
And using this line of code we are inserting it at the tail.
So we are having a new node with value one.
And this is inserted over here.
And two is pointing to one at this moment.
And then we again calculate carry forward which is one divided by ten.
And we are flowing it which is equal to zero.
So now carry forward becomes zero and then L1 is falsy so L1 is just null and L2 is just null.
And then carry forward is also zero.
Again when we come over here we see L1 is null, L2 is null, and carry forward is zero.
So this becomes falsy and we come out of it and we are just going to return the linked list over here,
which is three pointing to six pointing to two pointing to one.
And that is the output.
So this is how this function works.
Now what about the space and time complexity of this solution.
The time complexity is going let's say we have two linked lists of length m and n.
Now we have to traverse the whole linked list.
Right.
So whichever is greater, that would determine the number of operations we need to traverse the linked
list.
So that's why the time complexity is going to be O of maximum among m and n.
And the space complexity is also equal to the same thing, because we are going to have an output array
output linked list, and the size of the output linked list can be maximum max of m comma n plus one.
Right.
So over here you can see we have an extra node over here compared to the length of the linked list because
there was something in the carry forward.
So that's why we can say the maximum length of the linked list is going to be maximum between M and
N plus one.
So that's why we can say the space complexity of this solution is also of the order of max of m and
n, where m and n are the respective sizes or lengths of the linked list which is given to us.