Hi, everyone.
So today we are going to solve this question cycle addiction.
OK, so what we have to do so given a long list, so we will be given a long list and we have to return
a boolean value whether the list contains a cycle or not.
So in this case, we can see it is a cycle.
So since they the cycle is a loop, we have to return.
True in this case.
OK, and if there is no cycle, then we can return false.
So this question is present only.
Good.
OK, so this is the problem now we can see here.
So since this contains this linked list contains a cycle, so we have to return to it was a continuous
cycle we have to return to.
In this case, there is no cycle, so we have to return false.
OK, so this is our challenge.
We have to solve this question using or question memory.
OK, so constant memory, basically open space.
So how are we going to solve this problem?
So the first approach to solve this problem is with the help of map.
OK, so how are we going to solve this problem with the help of MAP.
So the structure of map will be.
List North Star and a Boolean value, OK, so list North Star and also give a loopier.
So this will be Mekki and this will be my value.
So what I will do, I will add it over this link list.
Now I am standing here it so is it present inside the map.
So this is my map.
So initially my map is empty so I will check.
Is it pleasant inside the map.
No it is not.
So I will put it here then.
I will check.
Is one present inside the map.
No.
Then put it inside the map.
So is nine percent inside the map.
No it isn't so but nine inside the map.
OK, so is four present inside the map.
No it does not.
Then push forward inside the map.
So is to present.
No it is not.
Then Pushtu.
So is three present.
No Bush three seven present inside the map.
No Bush seven to present inside the map.
Yes it is present but no it is not present.
Why.
Because we are storing list North Star basically.
What is a list.
North Star.
So basically it is a pointer.
It is a pointer and it is pointing towards a..
So this node contains a value and a next pointer and led to the address of this snorers 800.
So basically List North Star contains 800.
OK, and obviously this node and this node, they will have different address.
For example, this node has a 700 and this node has addressed 900.
So basically at this point, I am storing 700, OK, and I'm comparing is 900 close to 700.
Not it is not.
OK, so basically we are comparing this north to not only the value.
OK, now we will check nine.
So is nine percent.
Yes, nine is present, but no it does not present because we have to compare both the values, we only
compare the value and we will also compare the next pointer.
OK, so basically this is nine.
This nine has a different address and this nine has a different address.
So nine is not present.
OK, then we will again come back.
To do so is to present.
Yes, two is present.
So its address is also seven hundred and its address is also seven hundred.
So since this is present.
So I will return to.
OK, so our output will be true now in this time.
So in this case, with the help of MAP, what is the time and the space complexities of time?
Complexity is basically linear.
We are just operating on the left and the space complexities when we are creating the map.
OK, so when the linked list does not contain a cycle.
So what will happen?
So this is let's say this is the list.
One, two, three.
So in this example, this list does not contain any cycle.
So it will happen.
So when one is inside the map, so initially the map is empty.
No one is not present.
Push one.
So to present.
No, it is not present.
Bush to three present.
No, it does not.
President Bush three.
Then I will come maternal and my linked list is over.
So basically I will return false.
OK, so the time complexities and the space complexities also big of an but the problem askers.
To do it in open space.
OK, so how we can solve this problem in open space, so this approach, which is called slow and fast
Brender approach.
OK, slow and fast point.
That approach now in slow and fast point, that approach.
What will happen.
So slow pointer.
I will take two pointers.
OK, I will take two pointer.
So the name of the first pointer is slow and the name of the second point that is fast.
OK, so if a slow pointer takes a jump of one, then fast pointer will take a jump of two.
OK, so fast pointer will run twice the speed of slow pointer.
OK, so how we can use this approach of slow and fast point in this question.
OK, now let's first draw the diagram.
OK, let us first take an example.
We will take a big, big example to understand.
OK, so let's say this is it then.
I have one nine four again let's say two.
I am taking the same example, the example that we discussed above.
OK, so three, then seven, then let's say two nine.
And this is two again.
OK, so this is my long list and now we will try it in our slow and fast pointer approach.
We will see how and how this law enforcement approach will help us to solve this problem.
OK, so as we discussed, we will take two pointers low and fast.
So initially, both slow and fast pointer, they will be present at the head of the list.
So this is the head of the linked list.
So initially, both slow and fast pointer are at present.
At present at the head of the linked list.
Now lowpoint, they will take a jump of one and fast point.
They will take a jump of two.
OK, so after one jump, what will happen?
Slow pointer will come here.
And at the same time, first point they will take a jump of two.
So fast pointer will come here.
OK.
Now, again, slow, that will take a jump of one, so slow pointer will come here.
Now, first point, I will take a jump of two, so one and two, so first point, I will come here.
OK, now, slow point.
We'll take a jump off one, it's this low point that will come here.
Now, point I will take the jump off to.
So one and two, so first point, I will come here now against lowpoint, jump of one.
Fast point to jump off, too, so this is fast now, slow appointer takes a jump of one.
This is slow.
Fassbinder, take the jump off one and two.
Now, see, slope equals fast point.
So at the point at the moment of time when slow equals fast, slow and fast point that they are equal,
that means there is a loop.
That means there is loop or basically cycle in the long list.
OK, so how we can see when slow and fast point our meeting then.
On what basis I can say slow.
There is a cycle in the long list because think like this, a person is moving at a speed of X and another
person is moving with the speed of two X, so and then they are meeting so they can only meet when there
is some cycle, ok.
They can only do it when they do some cycle.
For example, let's say this is the structure.
So this is the first person and this is the second person.
So the second person is moving twice the speed of the first person and they are meeting.
So if if there's a straight road, then obviously this is the first person, this is the second person,
then these two person can never meet, OK?
Because the second person is twice is running with twice the speed of the first person.
And if there is a straight they will never meet.
They can only meet when there is a cycle, OK, only when they the cycle then only they can meet.
OK, so this problem, this slow and fast pointer approach, this is also used to find the midpoint
of the linked list.
OK, so how we can find the midpoint of a long list.
So suppose so.
Suppose this is a long list.
So what will happen.
Slow and fast.
Point the boat out here.
So slow pointer will move with the speed of one basically X and point will move with the double speed,
then slope will come here and fast pointer will reach the end of the linked list.
So when the fast pointer reaches the tail of the linked list, then at that time the slope pointer will
be at the middle point, the midpoint of the linked list, obviously.
OK, so slow pointon fast pointer.
Initially they both were present at the height of the list, but the slope point is moving.
The speed of X and fast pointer is moving with the speed of the weeks.
So when the fast pointer will reach the tail then obviously the slope when they will reach the midpoint.
OK, so this approach, this fast and slow pointer approach, this is also used to find the midpoint
and we are using that.
We are using that same approach to detect whether there is a cycle in the linked list or not.
OK, so now let us implement both the approach.
So let us implement.
I am implementing both the approaches.
OK, so.
First, let us implement the map approach.
OK?
So let's not start and bull, let's say the name of the map is my map, so what we have to do, we simply
have to it over the linked list.
So while it's not a closed tunnel.
Now, what we have to do.
Check whether this note is present inside the map or not.
OK, so my map not count.
A, if the north is pleasant inside the map, that means there is a cycle, if there is a cycle, we
can simply return true from here.
Otherwise, what we have to do, we will push this node inside the map, so my map of a.
It's basically true.
And at the end at the end of the Vilo begins and it unfolds.
OK.
OK, so basically spelling mistake.
OK, so we are returning to and output is false.
OK, so whether the mistake equals the next offie.
OK, so our court is working.
Time, complexity of this map approach is basically one time and one space.
OK, so how does current function works?
So basically this can't function, this can't function will count how many times the node appears inside
the map.
OK, so.
The count can be zero or the count can be any positive integer, OK, so that only two values in the
count will be zero.
So if the zero, that means the node is not present.
And if the count is a positive integer, that means it is Besant.
OK, so then we will return.
True.
So we will only return true only when the output is a positive integer.
So the output is a positive integer.
This condition will become true.
If this condition is true, then only we are returning.
OK, so the complexities oint and the space complexities also join.
OK, now let us implement this law and the Fassbinder approach.
So we need two pointers and initially both the pointers will point towards the head of the linked list.
So slow is pointing towards a and similarly, the fast pointer is also pointing towards a OK now fast
point.
I will run with twice the speed of X so while fast and then the next of fast.
So why I'm doing this, why the condition is this because fast has to take doorjambs.
So fast is going to take two jumps, so fast is next off, next of fast.
Fastest making two jumps and slow will take only one jump.
Slow, slow, slow equals the next slow.
And if at any point slow and fast article, that means there is intersection, OK, that means there
is a loop in the linked list.
OK, and finally we can return false.
So let's test with good.
OK, so our court is working, so the complexity of this slow and fast winter approaches or in one speech.
Now you might get confused why I have written this condition first and next of.
So basically, take this example.
One, two, three.
OK, and let's say for so fast is currently at the head position so fast is going to take two jumps.
OK, fast is taking two jumps so fast.
It was next of next door faster.
So basically fast likely wants to come here.
OK, so in this case fast exist and the next hour fast exist so I can reach here so fast will come here.
Now, when this loop will run again, so what will happen?
Let's take one more example.
OK, now fast exist and the next fast exist.
So fast can take two jumps, fast can come here.
Now, at this point, I will again check Flast exist and the next office does not exist, since the
next afast does not exist, I will not go inside the loop.
I will reach here and I will return false.
OK, so basically, in short, this condition, because I'm going to take two jumps.
So here I am digging doorjambs.
So to avoid the segmentation fault, we have to put this condition.
OK, try to think in this manner when I take only one jump.
So when I write EQUASS the next toffy when I take only one jump.
So what is my condition?
My condition is very simple.
While it is not external.
OK, so this is my condition when I do quiz next of it, because if the value of it is nil.
Then I will get segmentation fault.
That's why I have only one condition, but now I am going to take two condition here.
I have to condition first and the next of first.
OK, so because I am going to take two jumps, so I have to take two conditions to avoid the segmentation
fault or to avoid that entire matter.
So basically this means wildfire's is not a question or basically while fast exist and the next of fast
exist.
OK, this is essentially this only.
That was a short way of writing.
OK?
OK, so our goal is working, so there is no need to write this thing, you can simply write very fast
exist and the next fast exist.
OK, so to avoid segmentation fault, we have to avoid runtime error.
OK, so that's why we have to two conditions here, OK?
So I hope this court is fine.
If you have any doubt, you can ask me.
Thank you.