1 00:00:00,650 --> 00:00:01,940 Hello, everyone, and welcome back. 2 00:00:02,240 --> 00:00:06,170 In this section, we're going to talk about cycle detection in linked lists. 3 00:00:06,950 --> 00:00:09,410 So cycle detection is exactly as it sounds. 4 00:00:09,410 --> 00:00:14,030 We are trying to figure out if a link list has a cycle within it. 5 00:00:14,540 --> 00:00:19,610 And if you remember, when we first introduced link lists, we talked about the possibility of a cycle 6 00:00:19,610 --> 00:00:25,340 existing, which is where one lists node points to another list node that has already appeared in the 7 00:00:25,340 --> 00:00:28,110 linked list before, which gives us a cycle. 8 00:00:28,760 --> 00:00:33,020 The problem with cycles is that you've already seen we do questions. 9 00:00:33,020 --> 00:00:39,230 We receive linked lists as a head node and from that head node, we have to traverse one note at a time 10 00:00:39,230 --> 00:00:40,780 through out the link list. 11 00:00:41,570 --> 00:00:49,550 There's a chance if we have a cycle in our linked list that we can never know if we are actually within 12 00:00:49,550 --> 00:00:55,910 the cycle, meaning that we've navigated to the same node multiple times over and over again when we 13 00:00:56,030 --> 00:01:02,030 go through our sequence of calling current node, next current node, next current node, next, we 14 00:01:02,030 --> 00:01:06,440 could just be calling DOT next within the circle of this cycle that we see here. 15 00:01:07,380 --> 00:01:13,440 So when we think about a second, we're trying to detect a cycle in a linked list, what's happening 16 00:01:13,440 --> 00:01:18,600 is we're usually trying to figure out where the note that begins the cycle is. 17 00:01:18,600 --> 00:01:23,070 And in our case right here, it's that third list known from that third list. 18 00:01:23,070 --> 00:01:24,840 Note the cycle begins. 19 00:01:25,410 --> 00:01:31,290 So how do we, through our code, figure out if a cycle exists in our linked list? 20 00:01:31,530 --> 00:01:38,010 And even better, how do we identify the list node that starts the cycle, which in our case here is 21 00:01:38,010 --> 00:01:39,840 this third green list node? 22 00:01:40,650 --> 00:01:43,170 Well, there's actually a bunch of different approaches. 23 00:01:43,260 --> 00:01:49,470 And the first approach we might take that jumps to our mind is the naive approach where we keep track 24 00:01:49,470 --> 00:01:51,110 of every listener that we've seen. 25 00:01:51,630 --> 00:01:55,730 So here I've replaced these lists, nodes with numbers just so it's more clear. 26 00:01:56,070 --> 00:02:00,810 And what we would do is we would instantiate some kind of pointer starting from the head. 27 00:02:01,680 --> 00:02:05,970 What we would do is we would navigate through and keep track of every list node that we've seen. 28 00:02:05,980 --> 00:02:11,780 So here we've seen the one and we navigate to the two and we see that we haven't seen this node before. 29 00:02:11,790 --> 00:02:12,390 So we add it. 30 00:02:12,990 --> 00:02:20,120 We do the same thing with the three and the four and the five and the six and the seven and the eight. 31 00:02:20,550 --> 00:02:26,790 And now when we navigate to the three, we see that we've seen this three before, which immediately 32 00:02:26,790 --> 00:02:35,460 then tells us that we have not only a cycle inside of this list, but the three is where that begins. 33 00:02:36,300 --> 00:02:41,600 So now that we understand the idea behind how to do this, let's just quickly code this out. 34 00:02:42,390 --> 00:02:49,320 So here we are inside of our tablet and remember that what we're trying to do is we are just trying 35 00:02:49,320 --> 00:02:55,650 to navigate through our link list, one node at a time, keeping track of every little note that we've 36 00:02:55,650 --> 00:03:01,020 seen until we encounter a list node that we have seen already. 37 00:03:02,230 --> 00:03:08,080 So in order to do that, we know we need two variables, we need one thing that will keep track of the 38 00:03:08,080 --> 00:03:09,160 current know that we're on. 39 00:03:09,430 --> 00:03:14,260 So we're just going to set the current note, as we all have always done, and we need some kind of 40 00:03:14,260 --> 00:03:16,940 data model that will keep track of these little notes. 41 00:03:17,710 --> 00:03:22,960 So here, let's just first set current node, current node we already know how to do. 42 00:03:22,960 --> 00:03:26,080 It's just going to instantiate as the head node. 43 00:03:27,340 --> 00:03:32,560 As for the scaling data model that's going to keep track of every node we've seen, I'm going to use 44 00:03:32,560 --> 00:03:34,630 a data model known as a set. 45 00:03:35,320 --> 00:03:40,390 Now, a set exists in pretty much every single language and it behaves the exact same. 46 00:03:40,840 --> 00:03:46,090 A set is pretty similar to an array and a Hashmat combined. 47 00:03:46,570 --> 00:03:53,170 What happens is that with a set object, you can imagine that you can add values into it using some 48 00:03:53,170 --> 00:03:55,870 method that's on it, usually the add method. 49 00:03:58,010 --> 00:04:05,720 And what it will do is it will add in whatever value that you pass to it inside of this collection. 50 00:04:06,910 --> 00:04:13,300 You can then also call a DOT has method, and what this will do is when you pass it of value, it will 51 00:04:13,300 --> 00:04:17,400 check inside to see if that already exists. 52 00:04:17,410 --> 00:04:19,720 If it does, it will return you back. 53 00:04:19,730 --> 00:04:20,290 True. 54 00:04:20,950 --> 00:04:23,320 If it doesn't, it will return you back. 55 00:04:23,320 --> 00:04:23,900 False. 56 00:04:24,190 --> 00:04:25,260 So that's the whole thing. 57 00:04:25,270 --> 00:04:32,050 It's very handy and it's a really good object because it's optimized by most languages to add and check. 58 00:04:32,050 --> 00:04:36,370 This has in of one time, which is great for us because that's what we need. 59 00:04:37,250 --> 00:04:43,400 So here, what we want to do is we want to use the set objects and in JavaScript it's a class, so to 60 00:04:43,400 --> 00:04:47,000 use it, we can just say const cenotes. 61 00:04:49,330 --> 00:04:56,020 Is equal to the new set, which will instantiate an instance of the set class for us. 62 00:04:57,190 --> 00:05:05,860 Now, what we want to do is we want to advance our current note through this link list until are seen, 63 00:05:05,860 --> 00:05:08,920 nodes set has seen a node before. 64 00:05:09,070 --> 00:05:14,110 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 65 00:05:14,110 --> 00:05:15,940 say bang seen nodes. 66 00:05:25,930 --> 00:05:32,620 So just going over this, as I mentioned, cenotes has this method called has you pass it some value, 67 00:05:32,620 --> 00:05:38,890 which in our case is the current note that we're on and it will check and see has this current node 68 00:05:38,890 --> 00:05:45,340 been stored inside of it already in our case here with our initial value at this head? 69 00:05:45,610 --> 00:05:53,080 Of course, this set is empty, so this will give us back false because it has not seen the head value. 70 00:05:54,160 --> 00:06:00,400 But while it traverses and we store every value when we get back to the three, which we would have 71 00:06:00,400 --> 00:06:06,940 stored inside of the code that we're about to write, then see notes that has will return true this 72 00:06:06,940 --> 00:06:13,080 bang, we'll reverse that to false because bang takes true or false and it flips it to the inverse value. 73 00:06:13,210 --> 00:06:20,580 In our case, if C has returns us true, we want to reverse it to false so that our while loop breaks. 74 00:06:21,400 --> 00:06:24,400 So let's write the code and it will make more sense as we keep going. 75 00:06:25,590 --> 00:06:32,550 So what we're going to say is that inside of here, we actually need to also make sure that we are checking 76 00:06:32,550 --> 00:06:36,510 to see if any of these nodes next value is null. 77 00:06:37,110 --> 00:06:44,190 Because if one of these values is not a list note and it points to null, that means we actually are 78 00:06:44,190 --> 00:06:45,270 pointing to the tail. 79 00:06:45,900 --> 00:06:49,610 And the moment that there's a tail, we know that there actually is no cycle. 80 00:06:49,620 --> 00:06:54,720 So we want to make sure that our solution accounts for what happens if there isn't a cycle in the link 81 00:06:54,720 --> 00:06:55,400 list as well. 82 00:06:55,650 --> 00:06:57,420 And we're going to do that check first. 83 00:06:59,160 --> 00:07:04,590 Now, the reason why we want to do this check first is because we don't want to set current node in 84 00:07:04,590 --> 00:07:08,390 any way or advance our code the moment that we know where to tail. 85 00:07:08,400 --> 00:07:10,580 In fact, there's nothing else left to do. 86 00:07:11,280 --> 00:07:13,530 So we'll say if current node next. 87 00:07:15,500 --> 00:07:16,850 Is equal to No. 88 00:07:18,440 --> 00:07:24,710 We're at a tail and we want to return false from our entire function, meaning there's no cycle. 89 00:07:26,120 --> 00:07:32,990 What we do if the current node is a node is we want to add the current node to arsène node set, so 90 00:07:32,990 --> 00:07:34,580 we'll say seen nodes. 91 00:07:40,280 --> 00:07:42,050 And then we're going to say current node. 92 00:07:44,500 --> 00:07:46,070 Equals current no dot next. 93 00:07:46,120 --> 00:07:48,430 We're just advancing current node forward. 94 00:07:50,020 --> 00:07:50,740 And that's it. 95 00:07:50,770 --> 00:07:52,090 That's all our world needs to do. 96 00:07:52,780 --> 00:07:56,590 So as we walk through this, what will happen is we're going to add. 97 00:07:56,590 --> 00:07:57,280 We're going to add. 98 00:07:57,280 --> 00:07:57,880 We're going to add. 99 00:07:57,880 --> 00:07:58,450 We're going to add. 100 00:07:58,450 --> 00:07:58,930 We're going to add. 101 00:07:58,930 --> 00:07:59,380 We're going to add. 102 00:07:59,380 --> 00:08:00,010 We're going to add. 103 00:08:00,010 --> 00:08:07,900 And then when we come here are while Loop will fail and we are now current node set at three because 104 00:08:07,900 --> 00:08:09,160 our code is always advancing. 105 00:08:09,190 --> 00:08:14,550 So when it's at eight, it's going to store eight, but it's also going to advance it to the next value. 106 00:08:14,560 --> 00:08:18,430 It's going to advance our current node points are from eight to eight next, which is three. 107 00:08:18,970 --> 00:08:22,180 This three is going to get checked inside of our no has. 108 00:08:22,390 --> 00:08:27,250 It's going to see that three is already inside of it because we passed by it earlier when we first started. 109 00:08:27,790 --> 00:08:32,770 And then we are going to break our while loop and we're just going to return the current node value, 110 00:08:32,770 --> 00:08:36,280 which indicates the node that the cycle begins. 111 00:08:36,730 --> 00:08:39,940 So here we want to return current node. 112 00:08:43,760 --> 00:08:44,550 And this is our code. 113 00:08:46,060 --> 00:08:52,180 Now, earlier on, I mentioned that this was a naive approach because there does exist an algorithm 114 00:08:52,180 --> 00:08:54,010 that makes this more performant. 115 00:08:54,280 --> 00:08:58,150 So let's quickly break down the space and time complexity of this solution. 116 00:08:59,150 --> 00:09:05,600 So when we think about the time complexity here, we see that we're advancing current node until we 117 00:09:05,600 --> 00:09:09,920 see a value, if there is a cycle, meaning that we touch every node only once. 118 00:09:10,250 --> 00:09:18,890 So time complexity is O of end, you might be wondering this set objects has and this add method. 119 00:09:18,920 --> 00:09:20,990 What is the time complexity of this? 120 00:09:21,470 --> 00:09:24,050 Most of the time with sets almost all of the time. 121 00:09:24,050 --> 00:09:29,810 Actually they are extremely optimized by the underlying language, which means that they use the best 122 00:09:29,810 --> 00:09:34,220 practices and underlying they use the appropriate hash map or the array. 123 00:09:34,700 --> 00:09:40,270 And what will happen is that the has and the add method you can assume has O of one performance. 124 00:09:40,790 --> 00:09:46,160 I'm going to link you the documentation for the set inside of JavaScript so you can take a look. 125 00:09:46,160 --> 00:09:47,820 There's actually two bits of documentation. 126 00:09:48,080 --> 00:09:50,840 One is the API, which shows you what these methods do. 127 00:09:50,870 --> 00:09:54,950 The other is it explains the performance speed of has an ad. 128 00:09:55,490 --> 00:09:57,580 This is pretty much the same across all languages. 129 00:09:57,590 --> 00:10:00,950 So you can assume of one for half of one for ad. 130 00:10:02,240 --> 00:10:05,900 And this yields us a time complexity of of an. 131 00:10:07,790 --> 00:10:15,950 So as for our space complexity, we know that this set is a scaling data structure because we keep adding 132 00:10:15,950 --> 00:10:20,970 every node in until we reach the first instance where a node has been seen before. 133 00:10:21,170 --> 00:10:26,330 So this means that we are storing every single node inside of this link list inside of our scaling data 134 00:10:26,330 --> 00:10:26,660 model. 135 00:10:27,020 --> 00:10:30,990 So if the link list grows, so does the amount of list nodes that we store. 136 00:10:31,400 --> 00:10:35,780 So here we see we have a space complexity of oh, of end as well. 137 00:10:36,750 --> 00:10:42,060 Now, in most interviews, this method for psycho detection is probably enough, but if you're going 138 00:10:42,060 --> 00:10:46,740 to interview at a premier tech firm like any of the FANG companies, they are going to want you to know 139 00:10:46,740 --> 00:10:51,930 the optimal solution, which is known as Floyds Tortoise and Hare algorithm. 140 00:10:52,560 --> 00:10:57,990 So Floyds Tortoise and Hare algorithm will reduce our space complexity to oh of one while maintaining 141 00:10:57,990 --> 00:11:00,150 a time complexity of O of N. 142 00:11:00,270 --> 00:11:03,000 And I'm going to show you how we can implement that in the next lesson. 143 00:11:03,300 --> 00:11:08,130 Before I do that, I just want to mention that this code does exist in a rebel file in this resources, 144 00:11:08,460 --> 00:11:13,920 and I've also instantiated the list node for you so that you can run through it and add any console 145 00:11:13,920 --> 00:11:17,820 logs to our code to make sure you understand everything that's happening here. 146 00:11:18,210 --> 00:11:22,590 Walking through the code is going to be identical to what we did earlier in this lesson when we showed 147 00:11:22,950 --> 00:11:26,010 how the pointer storing the values is going to be. 148 00:11:26,370 --> 00:11:29,640 It's just that here we want to write it out because it's always good practice. 149 00:11:30,210 --> 00:11:34,980 So if you want to reference and make sure you understand everything here, use the rebel file. 150 00:11:35,980 --> 00:11:38,950 Otherwise, let's move on to Floyds Tortoise and Hare algorithm.