Welcome back.
In this video, let's try to think how we can solve this question.
Now let's say the linked list which is given to us is this one over here.
So you can see there is a cycle right which is starting at node three.
Now what would be the brute force method of solving this question.
We could use a hash table for example.
And as we go along the linked list using the dot next operation, we will keep storing the nodes that
we have visited.
And then we will just see whether we are coming back to a node which was already visited previously.
So that would be the brute force way of solving it.
So let's just walk through it.
Let's say the hash table is visited.
We call the hash table visited and it's initially empty.
Now we are at the head.
So we have visited this node.
So we say that one.
And then that's the key and the value is true.
And then we use the next operator.
So we come to the next node which is two.
And we mark it as visited.
And then we go to three.
We mark it as visited.
And we keep doing this till we get to nine.
So all these nodes are going to be marked as visited in our visited hash table.
And then when we again you follow the next pointer, we are going to come back over here, which is
at node three.
And at that point we will see that it is already there in our hash table.
So it's there already over here.
And therefore we know that there is a cycle or this, this linked list over here has a cycle and we
can just return the node three.
So this would be the brute force method of solving this question.
And what would be the complexity analysis of this question.
The time complexity would be O of N because we are traversing every node in the linked list.
And let's say there are n nodes in the given linked list.
And the space complexity also is going to be o of n, because in the hash table we are going to store
all the n nodes.
So the time complexity is O of n, and the space complexity for this solution is also O of n.
Now let's try to think whether we can solve this in constant space.
So again this is the linked list that we have.
And we are trying to solve this in constant space.
That is, we're going to try to check whether there is a cycle in the linked list, which is given to
us in constant space.
Now for this, we are going to use a very famous algorithm which is called Floyd's Tortoise and Hare
algorithm.
Now let's try to understand this beautiful algorithm.
So let's make some space over here.
Now we're going to use two pointers.
Let's call it t and h.
So T stands for tortoise and H stands for hare.
Now tortoise and the hare both are at the head at this moment.
Now the tortoise is going to just move one step at a time, but the hare is going to move two steps
at a time.
So let's trace how they are going to move over here.
So the tortoise moves one node and the hare comes over here because it moves two nodes.
Again the tortoise moves one node and the hare moves two nodes.
We keep doing that.
So the tortoise again moves one node and the hare has moved again two nodes.
And then the tortoise again moves one node.
And the hare has reached over here by moving two nodes.
And we keep continuing this.
So the hare is again going to move two nodes.
So after moving one node the hare is over here.
And then after moving the second node the hare is going to reach node four.
And the tortoise moves one node.
And then we again continue this.
The tortoise is going to one node and the hare moves these two nodes.
And next in the next step you can see that the tortoise is also reaching at node eight.
And the hare also is reaching at node eight.
So they have met.
And therefore we know that there is a cycle in the given linked list.
If there was no cycle, if there was no cycle, then the hare would have reached null, right?
So if there was no cycle, the hare would have reached the end the null pointer, right?
So at that point we would have known that there is no cycle and we would have stopped.
But in this case we can see that because there is a cycle.
Finally they are meeting and therefore we can be sure that yes, there is a cycle in the given linked
list.
All right.
Now let's now also see how to find where the cycle begins.
Because in the question it's mentioned that if there is a cycle, we have to return the node where the
cycle begins, which is this node over here.
So let's see how we can find this.
So we are going to have one pointer which is at the head.
And then there is going to be one more pointer which is where the the hare and the tortoise have met.
Or we can just use the tortoise pointer itself.
Now what we is going to happen is these two pointers are going to move one step at a time.
So let's move them.
So this pointer is moving one step.
And this pointer moved one step and reached over here.
Now again both of them are going to move one step.
And you can see that they are meeting over here right.
So they are meeting where the cycle begins.
So that's how we can find the node where the cycle begins.
And we can just return this node over here.
So this is how we can solve this question.
Now let's take a look at the complexity analysis of this method of solving this question.
Again the time complexity is going to be o of n because Max we are going to do n iterations.
Now you can notice that even though the hair is moving two times two nodes at a time, this is going
to have max n iterations, right?
Because the tortoise will not do more than n moves.
Now why is that?
So let's try to develop an intuition regarding this.
Now let's say when the tortoise is over here, the hair is going to be over here.
Right?
So the tortoise moves from here to here and then to here.
So it makes two steps.
So the hair is going to move from here to here and then from here to here.
So the hair is at node five and the tortoise is at node three.
All right.
Now if the hair let's say let's say the tortoise let's say the tortoise has to move x moves so that
they meet.
Now if the tortoise is doing x moves and they are meeting after these x moves, then we can say that
the hair will do n minus two moves plus x minus two, where n minus two is the number of nodes in this
cycle.
Right.
So if there are n nodes total we are just removing these two nodes which are not part of the cycle.
So that's n minus two over here.
And then you have x minus two over here because the hair is two nodes ahead of the tortoise.
So let's just try to understand this n minus two is the hair is doing one cycle.
And then after one cycle the hair is going to get back to here.
And then again it has to move from here.
From here the there are x moves right.
So wherever the tortoise reaches.
So the difference between this point and wherever the tortoise reaches is going to be x minus two.
Because you can see after doing one cycle the hair is ahead of the tortoise by two nodes.
All right.
So we have seen that when the tortoise moves x nodes the hair is going to do n minus two plus x minus
two nodes.
So again we are just trying to develop an intuition why the tortoise will not do more than n moves.
Now we know that the hair is moving twice at the speed of the tortoise, so we can say that two times
into x will be equal to what we have over here.
So we can say n minus two plus x minus two is equal to two x or x is equal to n minus four.
Right.
So x is equal to n minus four.
And that's how we know that they are meeting over here.
Right.
N is equal to nine nine minus four is equal to five.
And you have 1234 and five.
So that's how they are meeting over here.
You can see that the tortoise is not going to do more than n moves.
That is the tortoise is not going to cycle again over here.
Right.
So the hare might do multiple cycles depending on the length of the cycle and how how big this initial
part is.
But the tortoise is not going to do any cycle.
So the tortoise will do max n moves.
Let's say the hare somehow was here when the tortoise reached over here.
In that case we will have n minus two plus x minus one, right?
Because there is just a difference of one.
And we would have get x is equal to n minus three.
And in that case n minus three is nine minus three which is six.
And they would have met over here.
So that's the worst case right.
So in this worst case also the tortoise would have just done n moves.
All right.
So the time complexity of this solution is still O of n.
Now what about the space complexity of this solution.
Now remember we tried to get to a better solution because the previous solution was taking O of n space.
But in this case we are not using any extra space or any auxiliary space.
And therefore the space complexity of this solution is O of one.
So the time complexity is O of n and the space complexity is O of one.
And in the next video let's try to understand why.
If we have a pointer over here and the pointer at the place where these people are meeting, and if
we keep moving the pointers one at a time, why is it that they will again meet at the starting point
of the cycle?
So let's look at the proof for this in the next video.