Welcome back, everyone.
So hopefully you got a chance to try and cut out Floyd's hair and tortoise algorithm yourself, let's
just do it together right now here.
What we're going to do is we need to instantiate the hare pointer and the tortoise pointer, which are,
of course, the fast and slow pointers so we can instantiate them as hare and tortoise just because
it's more clear since it is the hare and tortoise algorithm and they both instantiate at the head value.
So tortoise is also going to start at the head.
And they, of course, are pointers and what we want to do is we want to loop over and over until either
the hare and the tortoise overlap at some less node or the hare is pointing at the tail.
Now, the reason why we want to make sure the hare is the one that checks for the tail is because the
hare is the one that moves faster.
So it will reach the tail before the tortoise if a tail does exist.
So here's what we're going to say, is we are going to use a while loop, accept any condition here.
Doesn't matter.
We want to loop what instead we want is we want to loop.
While true, what this means is that this while loop will continually run unless any code inside calls
the brake keyword brake will break out of the wire loop as a whole and end the while iterations.
But we want to keep looping our while loop until we have found either of our two cases.
So this is why we use while true, what we're going to say here is we are going to advance the hare
and the tortoise each one step forward.
So here here is equal to hair next.
And tortas is also equal to tortas dot next.
Now that they've both advanced one step, we need to think and consider that edge case I was mentioning
where the link were received does not have a cycle in it.
The other thing we have to consider is what happens if the linked list we receive is a single note the
moment we advanced our hair next, we are technically pointing to null because if we have a single node,
then this nodes next value is null.
So we have to check for both cases where we have a single node, but also where we have a tail.
So how we can check for that is we can say that if the hair.
Pointer is equal to No.
So that would be this case right here or the hardcourt next.
Is pointing to not.
Which means that we have a tail value.
Then we want to return false from our entire function, because clearly in both of these cases, there
is no cycle.
If this is not the case, then we want to advance the hair one more step so hair equals hair done next.
So through this, we have now advanced the hair, the two steps and the tortoise, the one.
Once we've advanced these steps, we now want to check if the hare and the tortoise are now overlapping
and we can do this with a simple if check that says if the tortoise.
Is equal to the hair, if they're both pointing at the same little node, then we want to break.
So here we can just right break, which is a bit of JavaScript shorthand.
We don't have to add our braces.
The moment that we break, we now know the hare and the tortoise are both pointing to that meeting point
listener.
So what we want to do now is instantiate the two pointers that will traverse together to see if they
can find the list node that represents the start of the cycle.
And here we can just let two pointers, one called P1, which instantiates at the head value and P2,
which instantiates at either the hare, the tortoise.
It doesn't matter.
They both point to the same value.
So here I'm going to say that it points to the tortoise.
And now that we have one MP two, we want to advance them together until they meet.
So we're going to use another while loop here.
And we're going to say while P one does not equal P two, then we want them to keep advancing.
So P one is just equal to P one.
Next P two is equal to P to Dot next.
And once this while loop breaks, meaning that one MP to have overlapped, as we saw, this is the list
node that represents the start of our cycle so we can just return either one or two.
So I'm going to turn one.
And that is the Floyds Hare and Tortoise algorithm, so looking at this, we see that what we were doing
is we are iterating through and times as far as our time complexity goes.
So time complexity is still going to be oh, of end because despite the fact that the hare moves two
steps forward, meaning that there's a chance that it might loop over and over again within the cycle
and touch multiple nodes over and over again.
Technically speaking, it's all happening within one while loop, which means that this iteration,
despite the hare touching possibly the same nodes more than one time, the code is only iterating nine
times until it reaches the meeting point.
In fact, it's less than an hour turtle pointer or our tortoise pointer, which moves slower, will
not ever step in a loop in the cycle.
So now that we know that, then we understand that our time complexity is then.
As for our space complexity, all we instantiate are four different pointers, which always point to
a single value.
So this means that we end up with a space complexity of o of one.
So here we see that this is why it's such a great solution, because we've managed to bring our space
down as much as possible and we've managed to keep our time out of end.
It's also a really easy algorithm to reason about, and it's relatively simple to implement.
The only trick here in terms of the technical implementation was understanding that we had to do, while
true, to run our loop, because if we took our condition that we needed in order to break knowing when
this tortoise was equal to the hair, we had a value of our tortoise and hare equal to the node that
we knew indicated the meeting point.
We could not have done this with the traditional method that we were used to while writing a while loop
where we put the condition inside of the actual logic, because the reason why we can't do that is that
when we instantiate the function for the first time, hare and tortoise are both pointing to the head,
which means that this condition is equal when our while loop runs.
Initially, the only way that we were able to write this conditional while true loop and have a break
while aiming for the exact same goal, which is making sure that one of these pointers or both of these
pointers in this case, we're pointing to the appropriate less note that we were looking for was by
doing it like so where we had a while.
True, that would then break because we knew the moment that tortoise and the hare were equal after
running through a certain amount of iterations that we're unsure of what that would be.
The moment that they were equal, we knew that immediately we had our meeting point listener, so this
was really the only technical trick.
But now that we know what to do, if we ever encounter any cycle detection in a link less question as
either the main question or as the sub problem or a potential sub problem, we know exactly what to
do in order to detect the cycle.
Now, this is actually the exact same for doubly linked list as it is for singly linked lists.
The addition of the previous pointer doesn't change anything.
This method still works.
So we're at the point now where you might be wondering why is it that this method works if that question
lingers in your head?
There is a optional video that I'm going to show you in the next lesson that will prove why this method
is effective.
It does involve math and it does involve deriving functions.
So if you are interested in that, there's no need to watch.
It is entirely optional.
But I will say that you don't ever really need to know the proof when it comes to your interview.
It's really just for your own curiosity.
So if you're curious, definitely watch it.
I'm going to do it in the next video.
If not, you can easily move on to the next lesson after the next video.
So I will see you in whichever one you choose.