Welcome back.
Let's now go ahead and code the solution, which we discussed in the previous video, to check if there
is a cycle in the linked list which is given to us.
Now over here I have written the class node and using this I've created these nodes one, two, three,
four, five and six.
And then I've connected 1 to 2, 2 to 3, 3 to 4, 4 to 5 and 5 to 6.
And then I've made a loop over here so that we can test the code once we've written it.
So six is going to be connected to two.
All right.
So when we run the code and if we detect it correctly that there is a cycle, then we have to detect
that the cycle begins at two because six, which is the last node over here is again connected to two.
All right.
And then we are just setting head to be equal to one.
So once we write the function as described in the question, we will be passing the head of the linked
list to the function.
So let's go ahead and write the function.
So let's write it over here.
Now let's call this function check loop.
And this function is going to take in the head of the linked list.
All right.
Now, once we are inside the function, let's just check if the head is null.
So if not head, then we can just return null, which means that there is no loop, right?
So if the head itself is null, there is no loop.
And if it's just a single node.
So let's just check that.
If not head dot next.
That is, if there is just one node in the linked list.
In that case.
Also, we know that there is no loop and we can just return null.
All right.
Now if this is not the case let's proceed.
So let's have here and here is going to point at the head.
And we will have the tortoise also.
And the tortoise is also going to point at the head.
Now we are going to keep looping as long as the hair is not at null, and as long as the hair can move
two pointers, right.
So let's do that over here.
While hair and hair dot next.
Right?
So as long as this is true, we will keep looping.
So if there was no cycle in the given linked list, then this would keep looping as long as hair dot
next right.
Hair dot next would be uh becoming null when hair is at the tail, right?
So if hair is at the tail then hair dot next will not be, uh, will not be a valid node.
And it is it's going to be null.
So we're going to stop at that point.
All right.
So that's fine.
We can because the reason is that we want the hair to jump two nodes at a time.
And if hair dot next is null.
And if we again call dot next on that it will throw an error.
So we want to avoid that.
So as long as this is not the case we keep moving forward.
So hair is going to move two nodes at a time.
So we can say hair is equal to hair.
Dot next dot next.
And the tortoise is going to move one node at a time.
So tortoise is equal to tortoise dot next.
All right.
Now once again inside this loop.
Also we will keep checking if the hair is equal to tortoise right.
Because if there is a loop this will keep going on without any end.
Because if there is a loop right there's a cycle.
So it's never going to be false.
So hair and hair dot next will never be false if there is a loop.
So if there is a loop, the way we come out of this while loop is if hair is equal to tortoise.
So that means they have met.
And in that case we will just break out of the while loop.
All right.
Now, once we are out of the while loop, let's check whether they have whether the reason for breaking
out of the loop was that they have met, or is it another reason, like for example, they have reached
the tail.
So let's check that over here.
So if.
Here not equal to tortoise.
That means they have not met.
And we came out of the while loop.
That means that there is no loop, right?
So there is no loop.
So we can just return null in that case.
Now, if that is not the case, it means that they have met.
And that's the reason that we came out of the while loop.
So now let's try to find where the loop or the cycle begins.
Let's try to find this now.
For this we will need a pointer.
Let's call it pointer itself.
And this is going to point at the head.
Now we will move the head and the tortoise one step at a time as long as they don't meet.
So while pointer not equal to tortoise.
We will keep moving them one step at a time.
So pointer is equal to pointer dot.
Next.
And tortoise is equal to.
Tortoise dot next.
So they are moving one node at a time and when they meet we come out.
And at that point we have identified the node where the cycle begins.
So we can just return the tortoise or the pointer.
So let's just return the tortoise over here and that's it.
So this is the solution to the code the solution to the question that we have seen.
So over here we have seen we are able to find whether there is a cycle or not in constant space.
Now that's that's as, as compared to the brute force solution where we would have need to have a hash
table or a set, etc., which will take O of n space.
Now let's take um, let's just call this function, let's walk.
Uh, let's call this function using what we have set up over here for testing.
So we will pass in the head and let's see what's happening.
So we will say check loop.
And we pass in the head.
And our expectation is that we should get back two which is the beginning of the loop.
So let's see what we are getting when we run the code.
Yes, we are getting two over here.
So that's this node right.
That's this node with value two.
Right.
So this is pointing to three.
And again yes that's a loop we know.
So yes that's correct.
Now what if we change this.
What if we change this.
And we say six dot next is equal to three.
In this case the cycle begins at node three.
And we should get back that node.
So yes we are getting that.
And what if we just comment this out.
That is if we are removing the loop in this case we should see that there is no loop and we should just
get null.
Yes that's true, we are getting null and let's say it's just null over here.
So if the input is itself just null in that case also we will get null which is true.
And let's say we have one more node.
So let's create one more node over here just for testing.
So let's say const seven is equal to new node and it has the value seven.
And let's say we are not connecting anything to it.
So that's just a linked list with one node.
And let's say we are passing this node over here to our check loop.
Right.
So in this case we also get null because there is just one node and there is no loop.
So yes our code is working.
Now let's just take this initial sample which we had where we had these six nodes.
And let's say six dot next is equal to three.
And let's walk through the code and try to understand what's happening over here.
So for this let's grab a pen.
All right.
So let's go ahead and draw this out so that we can visualize this in a better manner.
So we have one which is pointing to two which is pointing to three which is pointing to four which is
pointing to five.
And then that's pointing to six, and six is pointing to again, uh, let's just check that over here.
Six is pointing to three.
Right.
So six is pointing to three.
So let's draw that.
So this is how the linked list looks like.
And we are passing the head to the check loop function.
So again let's just change this over here we are passing the head right.
So that was the initial example which you're trying to walk through.
Now let's try to look at what is happening in the function that we have written.
So we are inside the check loop function.
And we see that the head is not null and head dot next is also not null.
So we come over here.
Now here is pointing at the head and the tortoise is also pointing at the head.
Now we are going to have this while loop.
So let's just walk through it.
So here is truthy.
And here dot next is truthy.
So we are inside the while loop.
And here is moving two steps.
So here comes over here.
And the tortoise moves one step.
So tortoise is over here.
Now is are these two equal?
No, they are not equal.
So again is here truthy.
Yes.
And is here dot next.
Truthy.
Yes.
So we come again inside the while loop.
And the hair is moving two steps.
So it comes over here.
And the tortoise moves one step and it comes over here again we see that the condition is true.
So we are inside the while loop.
The hair moves two steps.
So it comes over here.
And then it comes over here.
And when the hair comes over here the tortoise moves one step and comes over here again.
The hare and the tortoise have not met.
So we are again moving.
So we come inside the while loop.
Again.
The tortoise is going to move one step and the hair is moving two steps.
So the hair comes over here and the tortoise also when it moves, one step comes over here and you can
see that they have met.
Right.
So the hare and the tortoise is at this point have met.
And both of them are at node five.
So we are going to have one pointer.
So this is going to be pointer.
And then we have the tortoise right.
That's what we are doing over here.
We see that the hare uh is the hare not equal to the tortoise.
No that's not the case.
They have met so we don't return null.
So we come over here and we have a pointer which is pointing to the head.
And then while the pointer is not equal to the tortoise, we are going to move them one step at a time.
So the pointer comes over here.
And the tortoise comes over here.
And again they are not equal.
So again they move.
The pointer comes over here and the tortoise also comes over here.
And at this point they are both pointing to node three.
And therefore we come out and we are going to just return the tortoise which is node three.
And that is the beginning of the cycle.
So this is how this function works.
Now let's take a quick look at the space and time complexity of this solution.
Now what about the time complexity.
The time complexity is going to be O of N because over here in the while loop you can see we will keep
looping as long as either the hair should reach the tail right, the hair should reach the tail, or
the hair should be equal to the tortoise.
So if the hair reaches the tail, that's n operations.
And if that is not the case, they will meet before the tortoise does n moves, right.
So we have seen that in the previous video.
So over here we are going to do maximum n operations.
And then once that is done over here we are going to do less than N operations to get the pointer and
the tortoise to meet.
So that's why the time complexity of this solution is O of n.
And the space complexity of the solution is just O of one, because we are not using any auxiliary space.
So this solution runs in constant space.