Hello, everyone, and welcome back.
In this section, we're going to talk about cycle detection in linked lists.
So cycle detection is exactly as it sounds.
We are trying to figure out if a link list has a cycle within it.
And if you remember, when we first introduced link lists, we talked about the possibility of a cycle
existing, which is where one lists node points to another list node that has already appeared in the
linked list before, which gives us a cycle.
The problem with cycles is that you've already seen we do questions.
We receive linked lists as a head node and from that head node, we have to traverse one note at a time
through out the link list.
There's a chance if we have a cycle in our linked list that we can never know if we are actually within
the cycle, meaning that we've navigated to the same node multiple times over and over again when we
go through our sequence of calling current node, next current node, next current node, next, we
could just be calling DOT next within the circle of this cycle that we see here.
So when we think about a second, we're trying to detect a cycle in a linked list, what's happening
is we're usually trying to figure out where the note that begins the cycle is.
And in our case right here, it's that third list known from that third list.
Note the cycle begins.
So how do we, through our code, figure out if a cycle exists in our linked list?
And even better, how do we identify the list node that starts the cycle, which in our case here is
this third green list node?
Well, there's actually a bunch of different approaches.
And the first approach we might take that jumps to our mind is the naive approach where we keep track
of every listener that we've seen.
So here I've replaced these lists, nodes with numbers just so it's more clear.
And what we would do is we would instantiate some kind of pointer starting from the head.
What we would do is we would navigate through and keep track of every list node that we've seen.
So here we've seen the one and we navigate to the two and we see that we haven't seen this node before.
So we add it.
We do the same thing with the three and the four and the five and the six and the seven and the eight.
And now when we navigate to the three, we see that we've seen this three before, which immediately
then tells us that we have not only a cycle inside of this list, but the three is where that begins.
So now that we understand the idea behind how to do this, let's just quickly code this out.
So here we are inside of our tablet and remember that what we're trying to do is we are just trying
to navigate through our link list, one node at a time, keeping track of every little note that we've
seen until we encounter a list node that we have seen already.
So in order to do that, we know we need two variables, we need one thing that will keep track of the
current know that we're on.
So we're just going to set the current note, as we all have always done, and we need some kind of
data model that will keep track of these little notes.
So here, let's just first set current node, current node we already know how to do.
It's just going to instantiate as the head node.
As for the scaling data model that's going to keep track of every node we've seen, I'm going to use
a data model known as a set.
Now, a set exists in pretty much every single language and it behaves the exact same.
A set is pretty similar to an array and a Hashmat combined.
What happens is that with a set object, you can imagine that you can add values into it using some
method that's on it, usually the add method.
And what it will do is it will add in whatever value that you pass to it inside of this collection.
You can then also call a DOT has method, and what this will do is when you pass it of value, it will
check inside to see if that already exists.
If it does, it will return you back.
True.
If it doesn't, it will return you back.
False.
So that's the whole thing.
It's very handy and it's a really good object because it's optimized by most languages to add and check.
This has in of one time, which is great for us because that's what we need.
So here, what we want to do is we want to use the set objects and in JavaScript it's a class, so to
use it, we can just say const cenotes.
Is equal to the new set, which will instantiate an instance of the set class for us.
Now, what we want to do is we want to advance our current note through this link list until are seen,
nodes set has seen a node before.
So what we're going to say is we're going to use a while loop to do this traversal and we're going to
say bang seen nodes.
So just going over this, as I mentioned, cenotes has this method called has you pass it some value,
which in our case is the current note that we're on and it will check and see has this current node
been stored inside of it already in our case here with our initial value at this head?
Of course, this set is empty, so this will give us back false because it has not seen the head value.
But while it traverses and we store every value when we get back to the three, which we would have
stored inside of the code that we're about to write, then see notes that has will return true this
bang, we'll reverse that to false because bang takes true or false and it flips it to the inverse value.
In our case, if C has returns us true, we want to reverse it to false so that our while loop breaks.
So let's write the code and it will make more sense as we keep going.
So what we're going to say is that inside of here, we actually need to also make sure that we are checking
to see if any of these nodes next value is null.
Because if one of these values is not a list note and it points to null, that means we actually are
pointing to the tail.
And the moment that there's a tail, we know that there actually is no cycle.
So we want to make sure that our solution accounts for what happens if there isn't a cycle in the link
list as well.
And we're going to do that check first.
Now, the reason why we want to do this check first is because we don't want to set current node in
any way or advance our code the moment that we know where to tail.
In fact, there's nothing else left to do.
So we'll say if current node next.
Is equal to No.
We're at a tail and we want to return false from our entire function, meaning there's no cycle.
What we do if the current node is a node is we want to add the current node to arsène node set, so
we'll say seen nodes.
And then we're going to say current node.
Equals current no dot next.
We're just advancing current node forward.
And that's it.
That's all our world needs to do.
So as we walk through this, what will happen is we're going to add.
We're going to add.
And then when we come here are while Loop will fail and we are now current node set at three because
our code is always advancing.
So when it's at eight, it's going to store eight, but it's also going to advance it to the next value.
It's going to advance our current node points are from eight to eight next, which is three.
This three is going to get checked inside of our no has.
It's going to see that three is already inside of it because we passed by it earlier when we first started.
And then we are going to break our while loop and we're just going to return the current node value,
which indicates the node that the cycle begins.
So here we want to return current node.
And this is our code.
Now, earlier on, I mentioned that this was a naive approach because there does exist an algorithm
that makes this more performant.
So let's quickly break down the space and time complexity of this solution.
So when we think about the time complexity here, we see that we're advancing current node until we
see a value, if there is a cycle, meaning that we touch every node only once.
So time complexity is O of end, you might be wondering this set objects has and this add method.
What is the time complexity of this?
Most of the time with sets almost all of the time.
Actually they are extremely optimized by the underlying language, which means that they use the best
practices and underlying they use the appropriate hash map or the array.
And what will happen is that the has and the add method you can assume has O of one performance.
I'm going to link you the documentation for the set inside of JavaScript so you can take a look.
There's actually two bits of documentation.
One is the API, which shows you what these methods do.
The other is it explains the performance speed of has an ad.
This is pretty much the same across all languages.
So you can assume of one for half of one for ad.
And this yields us a time complexity of of an.
So as for our space complexity, we know that this set is a scaling data structure because we keep adding
every node in until we reach the first instance where a node has been seen before.
So this means that we are storing every single node inside of this link list inside of our scaling data
model.
So if the link list grows, so does the amount of list nodes that we store.
So here we see we have a space complexity of oh, of end as well.
Now, in most interviews, this method for psycho detection is probably enough, but if you're going
to interview at a premier tech firm like any of the FANG companies, they are going to want you to know
the optimal solution, which is known as Floyds Tortoise and Hare algorithm.
So Floyds Tortoise and Hare algorithm will reduce our space complexity to oh of one while maintaining
a time complexity of O of N.
And I'm going to show you how we can implement that in the next lesson.
Before I do that, I just want to mention that this code does exist in a rebel file in this resources,
and I've also instantiated the list node for you so that you can run through it and add any console
logs to our code to make sure you understand everything that's happening here.
Walking through the code is going to be identical to what we did earlier in this lesson when we showed
how the pointer storing the values is going to be.
It's just that here we want to write it out because it's always good practice.
So if you want to reference and make sure you understand everything here, use the rebel file.
Otherwise, let's move on to Floyds Tortoise and Hare algorithm.