Hi, everyone.
So today we are going to solve this question intersection of two linked list.
OK, so we are provided with the Dooling list.
So this is our first linked list, linked list and this is our second link list linked list B, OK,
so we have to find the intersection point and the intersection point is seven.
OK, so this should be our output.
OK, so this is the first linked list starting from even and it ends at Citrix and this is our second
link list starting from BE1 and it will end it Sheetrit.
OK, and basically our intersection, we have to find the intersection.
So the intersection is seven.
OK, so this should be our output.
OK, we have to output this node.
So this question is present only record.
OK, so intersection of the two linked list.
So as you can see here, so this is the first example.
So linked list here for one eight four five and linked list B five zero one eight four five.
So our output should be eight.
OK, now let's see one more examples of included, which is zero nine one two four and linked list B,
which is three to four for output.
Should be two.
Now, here, this is a special case in this case, the English do not intersect, so the list is two
six four and the English is one in five.
OK, so in this case, our output should be nil.
OK, and these are some of the notes.
OK, so what we have to do.
So first of all, if the ruling list do not intersect, OK, if there is no intersection point, then
our output should be OK and we do not have to change the linked list, OK?
We do not change the linked list.
We will not change the structure of linked list must remain the same.
And we can assume there are no cycles.
OK, no cycle.
For example, this is the first linked list even if you a tree and suppose there is a cycle if one is
pointing towards a tree.
OK, so this is a cycle now in this problem cycle will not be there.
OK, we can assume there are no cycles and preferably I would call children at one time and one space.
OK, so we have to take linear time and constant space.
OK, now let us try to solve this problem.
So how we will approach this problem.
OK, so first of all, let us think about the brute force approach and very naive approach that we used
to that we used in Eddie.
OK, so what we can do here is so first what we will do.
So let us discuss approach number one.
OK, so brute force approach.
So the first so the first approach is.
Pick the first node and then I tripped over the second link list.
OK, they will not be any match, then pick the second or the first link list and again, I tripped
over the second link list again, there will be no match.
Then pick the third node and then again I did over that second link list.
Now, in this case, there will be a match.
OK, so if there is a match, we can output our result.
OK, and similarly, at this point, our program will stop and we will return soon.
OK, so this is what we will do.
So suppose we have to areas Eddie and Araby.
So Eddie has some elements, even E2 and E3 and Araby we when we do be three and before.
So the approach is very simple because the first element I did with the secondary pick, the second
element again, I did all the secondary.
The third element I did over the secondary picked the fourth element for telemedicine out there at eight
finished and we did not find any intersection point.
So that means at the and we do not intersect.
So in this case we can return.
OK, so this is the brute force approach.
So what will be the time and the space complexity?
So in the case of brute force, approach the time, complexities what we are doing here.
Let's do the list.
Let's say the length of the first Linklaters M and the length of the second link list is N, so the
time, complexities and doing OK and the space complexities of an OK constraint space.
Now let us try to call this OK.
So I will be writing C++.
So we are provided with the two link list, link list and linked list be OK and we have to return the
intersection point.
OK, so what is our approach?
So let's say.
It is not close to Nel.
Armatrading over the first link list, and now what I will do, I will select the first node, I will
select every note of linked list and then I will take over the list, be OK.
So since we have to ideato the second link list.
So I'm digging appointer now at this point that it will point it will point towards the head of.
So this is head.
Had to and this is pointing towards me, OK, now we have to did.
Over this link list, so while hairdo is not a questionable.
Now we just have to check.
OK, so we will check if a equals equals.
Head to.
Then we can return, there is an intersection point so we can return.
OK, otherwise what we have to do so.
Head to equals.
Head to head on next.
OK, and outside the wire loop.
Equals next toffy.
OK, now if the veil opens so we can safely say here.
So if the veil opened, then we can say there is no intersection point, OK, so we will have tunnel.
OK, so this is our very simple cold now let's try to end our good.
OK, so this will be had to.
OK, so our guard got accepted.
Now at let's try to it.
OK, so our goal is getting accepted, but it is not very good.
OK, so we can do optimisations.
So what optimization that we can do here is so first of all, the time complexity of this code.
So we discussed the first approach.
Which is the brute force approach, time, complexity is Emman and the space complexities own.
OK, let's discuss the second approach.
So the second approach will make use of map.
OK, so what we are going to do is so let us take an example.
So let us take one example.
So for one eight four five, so for one eight, four, five and we have second long list.
Five 01.
So this is five zero and one.
OK, so our output should be right now with the help of MAP.
How can we solve this problem?
So what we are going to do here is so this is our first linked list and this is our second linked list.
So pick any linked list.
For example, I am picking, let's say, second linked list.
You can pick it also, but let's say I am picking B, OK, now what we will do, we will take a map
and the structure of the map will be so the key will be node and the value will be, let's say a boolean
value.
True or false.
OK, so boolean value, true or false.
Now we will iterate over link list B, ok, suppose I am choosing wrinklies B so will I do it over the
second link list.
So what.
It will do so five.
First, five six five zero zero Drew when Drew.
Eight through, four through and five through.
OK, so this will be the structure of our map.
OK, so this will be our map.
So once our map is ready, what we will do, we will trade over the second link list, the remaining
link list, which we didn't choose.
OK, so I choose B for making the map.
Now I will iterate over the linked list.
OK, so Fort so is four percent.
So these are not values.
OK, so this is value but I am storing node.
OK, so basically I am storing five and I am also storing the address of its next node.
OK, I am not storing the value.
So this four and this four, they are not equal.
OK, I am storing the node I list or node.
OK, so this four and this four they are not a.
Please do not get confused.
So the structure of node is so it will store the value.
And I have a pointer next and this is the address.
OK, so when I am comparing the node we are storing node.
So when we are comparing the node we are comparing the value and we are also comparing the next pointer.
OK, so here I am storing two things.
Five and the next pointer.
So this four and this war, they are not equal.
OK, then I will compare, then I will compare one.
So is one present.
Yes, one is not present, one is present but they are not equal.
OK, not equal.
Why not equal.
Because the next pointer is different.
It now eight percent.
Yes it is present.
So here what will happen.
Value will we get matched and the next pointer will also get matched.
OK, because we are storing the node.
So since both the values get matched so we can return.
OK, so here we will return eight.
Return eight.
OK, so this is how we can use map.
Now what will the time complexity.
So the time complexity will be.
So first of all I am making this map OK, so we will use an algorithm.
Basically we can assume the access time is constraint, OK, or when existing.
So first of all I maltreating all the list B and let's say it's lent to them and it's Lento's.
And so first of all, am I taking over the linked list B to make the map.
So N then I will trade over the first link list.
And so the time complexities basically in place and all you can see, linear time, complexity, OK,
linear.
And what is this to respond collectively to, let's say, if I am choosing B, so those complexities
are often OK, so I am assuming here that this time of using the map is open.
OK, we are using an order to map.
Case.
So basically there are two types of maps.
First one is the unordered MEB.
And the second one is.
Map.
OK, so an order means basically we will use a hash table to implement the road map and for implementing
the map, basically we use a balanced body.
OK.
Basically, right BlackBerry now let us implement this approach.
So I will come into the school and I will write the code again.
OK, so first of all, we have to make an order to map.
Now, the road map, the key value will be the node.
And the value is bull.
OK, so let's say the name is my Miep.
Now, what we have to do, we have to pick and include, let's say I am picking B so to make our map
ready.
So while B is not well, I am maltreating or the second link list and what we have to do.
So my map of B is true.
OK, and then B equals next B.
OK, so at this point, our map is ready now what we have to do, we have to iterate over the first
link list.
So vile is not a personal.
And now we will check whether the node of the first linked list is present in the map or not.
OK, so if.
My map that count and I will give it.
So this can't function what it will do.
It will check whether the node is present in map or not.
OK, so if it is present, if the node is present in map, if the node is present in this map, that
means this node was also present in the second link list.
That means this is the common node.
OK, this is the other intersection.
So we can simply return a.
Otherwise, we will move ahead so equals.
Next.
OK, and if there's no intersection, we can simply a tunnel.
OK, so at this point there is an intersection.
OK, so what this current function will do, this current function will check whether this node is present
inside the map or not.
OK, so if this note is present inside the map, that that means this node was also present in the linked
list B, OK, that's then only there can be an intersection.
OK, so this is our complete code.
Not just try to run out of code and then we will submit.
OK.
So our code is getting a separate OK?
Our goal is right now we will discuss the best approach.
OK.
I'm commending the school.
Now let us discuss the best approach.
So we have discussed how to approach the brute force approach and the second one is my approach.
OK, so this is the time complexity.
So the time complexity is linear.
We do not have any problem with the time, complexity.
What we have problem is this space.
What do you want to do here is we want this space to be constant over the space.
OK, so this was the property of the problem, OK?
So the problem, access to solve this problem in linear time, in space.
So with the help of MAP, we can solve it in linear time, but it is taking on space and the space is
due to map.
We are we are creating map so that space is due to map.
We want to optimize it to constrain space now how we can solve this problem.
So what we are going to do here is so our approach will be very simple.
So this is the first linked list.
See when you do see three.
And let's say this, our second link list, so B1, B2, B3.
And before and then she went 23, OK, so what will you do?
We will CDC's linked list and this is linked list, so we will use a very simple approach, OK, and
approach will be first of all, we will find the length of linked list.
So let's say this is AMSO and is basically an toffy offline, Kristie.
So in this case, it will be one, two, three, four and five.
So this will be five.
Similarly, we will find the length of linked list.
So in this case, it will be one, two, three, four, five, six and seven.
OK, so this is seven.
Then what we will do, we will subtract these two.
OK, we will separate.
So basically we will do and minus him.
OK, so what will happen after this election?
After this election, we will get to OK.
So when we are separating.
So this is the common thing.
OK, this part is common in both the linked list.
So when we are separating the length of these two linked list, so this part will get deleted.
OK, so the differences basically do only so and minus mistal.
Now what is the value, what is the significance of this to let's call this the.
OK, so this is basically the difference between the difference of the lines between the two linked
list.
OK, let's call the OK now this is the big list B, so what we will do, we will make we will jump two
steps ahead.
OK, so we will jump two steps ahead.
So first to jump and the second jump.
So basically we are here.
OK, so we are standing at this point.
We are standing at this point.
OK, now what we will do so this is a and this is where we are currently standing.
OK, so these other two points now what we will do, we will move ahead in both the list.
OK, now these two points.
Point this one point to an end point victory, both these points are equidistant from the intersection
point.
OK, so both Evan and Bitly, they are equidistant from the intersection point while they are equidistant
because the difference was to OK, their defense was to and in the bigger list, I made two jumps.
Now, there's no difference.
OK, we are standing at equidistant from seven now, we will move ahead in both the linked list, so
I will move ahead then move ahead.
Move ahead.
And here will be our intersection point.
OK, so the approach is very simple, so step one, find the length of both the linked list finding
about the list.
Second, the defense of the link list take different.
Third step, move ahead.
EnLink list be OK, I'm assuming BS the bigger list, so move ahead and be how much we have to move
defense.
OK, now fourth point, they are equidistant.
OK, so both the points are equidistant.
From the intersection point.
And the fifth step is to move ahead in both the linked list.
Move ahead in both things list, either you will get the intersection point, all these new intersection
points, then we will return.
OK, so I'm assuming that mailing list is bigger one.
So if the mailing list is bigger, then I will lose SREP.
OK, now let us write the code.
So first of all, let us first write a function to find the list.
OK.
So I have a function.
Learned what it will take, it will take at least.
It will take the heart of the list and it will return the land, so initially the ground zero.
OK, so now let's say.
So while help is not a cold tunnel.
We have to look on placeless.
And then head Equis next of head.
And then they will return.
Count.
OK, so this is our land function and our time complexity of this land function is when.
OK, now.
What we discussed, we will find the length of both the linked list, so M is basically.
The length of the first list.
And is the length of the second longest.
Now we have to take the difference, OK, so defense.
Absolute function.
I am taking the absolute function because I don't know which one is bigger.
OK, and let's do.
And my him.
You can do a minus and also so absolute minus our would will be positive.
OK.
The significance of absolute now since we assumed that Lent that linked list is bigger.
So I'm checking my assumption here.
So if Mr. Thanin, then we will simply Swabian be OK?
We will simply step in and be now basically at this point, we can safely say BS, good, OK, BS,
a bigger list now if we have to do.
So as we can see here, we have to move ahead and be OK.
How much more weight difference?
So the defense was so.
Their defense was basically an DayQuil zero less in the and I placeless.
I have to move baby steps ahead in the second link list, submissively vehicles next of me.
Now, at this point, what is the scenario?
Both boat and they are equidistant from the intersection point and we are equidistant from the intersection
point.
OK.
Symbol, now, what we have to do, we will move ahead in both the linked list.
OK, so while it is not a question.
And simply.
These Nordquist tunnel.
I have to move ahead in both the list.
OK, so if it was close by, that means the intersection point.
So if it is intersection point, we can simplify it and way we can simplify it and be OK.
Otherwise A equals next of.
And B equals the next of B.
Now, if development, that means there is no intersection, so we will simply tunnel.
OK, now let's run our code and then we will submit.
OK, so line number 72.
OK, so.
OK, so now let's submit.
OK, so we're going to get some now see the difference first eight milliseconds, then 76 millisecond.
And this is our latest submission, 44 milliseconds.
And you can also see the memory.
OK.
Sixteen point nine memory.
Now, let us do so.
In this case.
Where is the time complexity?
So first, this land function, it will take time and again when time, then we are moving ahead basically
all the time.
And then in the worst case, when there's no intersection, it will take, let's say, basically let
us assume on time.
So basically the time complexity is linear.
OK, and blessin time, complexity is linear and space complexities or when we are not using any extra
space.
OK, so this is the best solution we have.
OK, this is the best solution.
So this was here, the time complexity was Emman and the space complexity was open and in this case,
the time complexity was linear, basically one.
And the space complexity, it was due to the map we have created.
OK, so this was Letwin and this is our best solution.
OK, time complexity is linear and the space complexities on OK, so this is how we can solve this problem.
OK, now there is one more way to solve this problem.
So the fourth we we will not implement this way.
But I'm just giving you a lot of idea that there also exist a fourth.
We know how we can solve this problem.
So even if you do and let's say this is even Seattle.
So again, B1, B2.
Vetri, and then she went on to do OK, so what we will do, we will start from me when we will reach
the end of the linked list and after reaching the end, we will save this node.
OK, so we will save this node and then.
I will make and I will make a second I will make a loop in the linked list.
OK, so what I will do, I will simply do 020 next equals.
OK, so this was a.
So now we have a loop in the list.
OK, now there is a problem.
The cycle in the linked list.
OK, Newtek cycle in list.
OK, so this is a very famous problem, I will also solve this problem, so the technical analyst,
this is a famous problem.
OK.
So with the help of this problem, if you have solved this problem.
So what we will do, we will be able to find this even OK, with the help of this problem, we will
be able to find Siwan.
OK, so this is our list.
We will start from BE1.
And if you have solved this problem, you can understand that we will be able to find even.
OK, if you do not know this problem, if you are unaware of this problem, then do not worry.
I will solve this problem later on.
OK, but here I just want to tell you that this is a very famous problem.
And with the help of this problem, they will be able to find even.
OK, now what we will do after finding this, even after we have the result.
So what we have to do, we have to remove this loop, OK?
We have to remove this link, OK?
Because the problem it mentioned clearly that we do not have to change the original structure of the
problem, original structure of the linked list.
OK, that's why I saved you two here.
OK, so that we can do to do it, Aaron.
Next is null.
OK, now after we know the solution of the problem, after we get to the seven, we will lose you to
our next question so that the structure of the list do not changes.
So the structure of English do not change.
OK, because this was a requirement of the problem.
OK, now.
Let's OK.
So if the question was detect if there is any intersection point.
OK, now the question was you have to simply return true or false.
OK, you have to return to the return type of the problem is bull and the problem is very simple detect
intersection point.
Basically redaction problem, OK, we have to detect the intersection point now, there are dueling
lists, even you and she wants you to see three.
This is between me to be three, and she wants you to see three.
Now, the problem that we have solved that problem, ask us to find the seven.
But now what I'm trying to say here is you have to return.
True or false.
OK, you have to return.
True or do you have to return false?
Basically, you have to detect whether to intercept or not.
OK, so one base you can use the above approach that we have discussed.
OK, but since.
It doesn't ask us to find out even then why we should find someone.
OK, we simply have to detect whether to north intercept, whether to intercept or not.
So what I will do, I will start.
So this is a I will reach the end point of it.
OK, so the end point of is three.
Then what I will do, I will start from B, this is B, and then I will reach the end point of B, so
then point of B is C three.
Now, if the end point, if the tale of A is same as the tale of B, that means there is intersection,
otherwise there is no intersection.
OK, simple.
You can also take this an example.
One, two and this is five and similarly selected three, four and five.
So in this case, the end point of the first list is five and similarly the end of the second linked
list is also five.
OK, so if the end point of both the same this intersection, if then if the end points are different,
there is no intersection.
OK, very simple problem.
OK.
So in this case, what you have to do is start from the first linked list, reach that point, start
from the second list which then point event for the simplest intersection.
So the time complexity will be linear and pleasant and basically the space complexity will be constant
space.
OK, or one space.
So I hope you got the idea of this problem.
If you have any doubt in this problem, you can ask me.
OK.
Thank you.