Detect & Remove Cycle in a Linked List | Floyd’s Cycle Detection Algorithm | DSA-One Course #39

This is DSA-One Course and in today's video, we will be solving a question on Linked List which is, Detect a cycle in a linked list. So basically, you are given a link list & you have to answer whether there is a cycle present in it or not. So, here I have given you 3 examples, where there is a cycle present in the link list. See, If you will try to iterate it then, 1 to 2, 2 to 3, 3 to 4, 4 to 5 and then again back to 3. then again, 3 to 4, 4 to 5 and again 5 to 3. This way you will be in a cycle, like stuck in a loop. So you have to observe going ahead, if this type of loop exists or not in this linked list. Lets take one more example, 1 to 2, 2 to 3, then again 3 to 2, 2 to 3, so again, 1-2-3-2-3-2-3-2-3 This way you will iterate infinitely Because the condition to iterate is, that while temp is not equal to null right, temp is not equal to null.

Here, temp will never be null because next of 3 is not null, it is 2 so you will keep iterating So you have to find out, if you see something similar in the linked list. detect a cycle Here also, there are only two nodes so there is a cycle present, 1 to 2, 2 to 1 so, 1-2, 1-2, 1-2, you will keep iteratating So you have to detect if such cycle is present or not. To solve this question, we will use a famous algorithm which is Floyd's Cycle Detection Algorithm But before that, lets have a look at how we will aproach it.

So, how can we know if there is any cycle present or not? So if you are iterating, and if any node gets repeated then it means that there is a cycle present. For example in this one, 1 to 2, 2 to 3, then again back to 2 So you are back on 2 right? So if we can make out that we are back on the same node again Then we can say that there is a cycle present. For that, we can make a hashmap. So make a Hashmap, and keep adding your elements in it when you iterate. So, you added 1 in the hashmap, then you check if 1 was already in the hashmap? If 1 was present it means there is a cycle present. But as we can see, 1 was not present in the hashmap so we added 1 in the hashmap After that, we went to 2, Now 2 is not in the hashmap, so we will add 2. Then we will come to 3, We will check if it is present in the hashmap. So, 3 is not in the hashmap so we will add 3. So next to 3 is 2, so we can see that 2 is already present in the hashmap so it means that there is a cycle starting from 'node 2' So, we figured out that there is a cycle present in this linked list.

And also from which node the cycle is present, which is node 2. So we answered both the question. This is one way, but here as you can see you will add all the nodes in the linked list in the map. Which means you are using the space, which creates a space complexity which is O(N) Time complexity is O(N), but space complexity is also O(N) So can we do this in a constant space? This is where Floyd's algorithm becomes helpful Basically, Floyd's algorithm solves this without using the hashmap means whithout using any space we can solve it.

And how does this work? so, it uses slow & fast pointers. Lets see how does that work, and then we will check its code. Lets take this example, here you can see a cycle exists in the link list, so how can we detect it using Floyd's cycle detection algorithm. So here we make 2 pointers, one slow & one fast. The slow poiner as you know will move one step at a time, while the fast pointer will move two steps at a time.

And we will let these pointers keep moving forward. And if the fast pointer reaches null, if the fast pointer reaches null, it means there is no cycle present but, if the fast pointer did not reach null & if the slow & fast pointer matches, it means that there is a cycle present. Lets understand again what I am trying to explain, In the beginning Slow & Fast will be pointing the Head. and after that they will keep moving forward. Slow will move one step forward & Fast will move two steps So slow will be here and fast will be two steps forward here. Are both of them at the same place? No both are not similar So lets move them forward. Again, slow will move 1 step forward & it will be here and fast will will move 2 steps forward, so fast will be here. so fast is here & slow one is here. They are still not matched, so again lets move them forward Slow again 1 step forward, so slow will be here Fast will move 2 steps forward so next to next. So, it will be here After that, again lets move slow 1 step forward so slow will be here.

Again Fast will move 2 steps forward so, next to next, fast will be here still they have not matched so again slow will move 1 step forward, so it will be here and fast will move 2 steps forward so, next to next so Fast will be here so as you can see, here Fast & Slow both have matched. As here both Fast & Slow have matched, it means that in this linked list, there is a cycle present. So this is the concept basically, it is very simple. It is not at all complicated. It is very simple talking of proof, what is the proof? The Proof is very simple. you might be understanding it intutively that we propelled both, the slow & fast now suppose there was a long link list, and then here was a small cycle present so we moved slow & fast forward, Slow moved 1 step at a time, slowly Fast moved 2 steps at a time rapidly then once the Fast pointer reached the cycle, it will keep circling there slowly, the slow pointer will also reach there and once the slow one will enter the loop, then at some point, both slow & fast will be at the same position and once they get matched, it means that a cycle exists there.

This is the basic concept and suppose there is a cycle present at the beginning of the link list Like, the cycle is present from the head itself, then also you will find it the slow one will move 1 step at a time right and once it reaches halfway the fast one would have completed his circle after that as soon as the slow one will reach here, your fast pointer will reach here after that, when your slow one will reach here then your fast one will reach here & both of them will again match at the head So, you can take any case like this and every time you can see that slow & fast will meet at some point surely if we move this way forward now if we want to find out, from which node our cycle is starting let's talk about this node Also, the question is that from which node does the cycle starts So we can also solve this question with this algorithm right now As you can remember, in the hashmap method if the node gets repeated, it means that the cycle is starting from that particular node.

But there, O(N) space was being used Here what we can do is first, let me tell you basically what happens later on we will also see the proof So once you see that Slow & Fast have met on this node So we put one pointer here suppose we keep the temp pointer here, and suppose here we put the current pointer and let's move both of them 1 step forward so from here, it will go here this will go here from here and this will go here and this will move here so both will match at this node Are you understanding? That here both slow & fast are meeting so from that point if you move 1 step forward at a time and simultaneously if you move 1 step forward from the head then guaranteed, you will meet at this intersection point Hope you are able to understand this If not then no problem, we will see the proof that how this is happening Basically, I am saying that suppose this was the point where the slow & fast met so from here, you have to move the pointer one step forward at a time and similarly, move one pointer forward from the head then guaranteed both the pointer will intersect here It is possible that the slow pointer will circle around the cycle many times until then the other one will slowly reach here but both of them will definitely meet at this point So now we will see the proof for this one that how does this work this is how we can make out at which node our cycle starts so let's see the proof for this one To understand the proof, let's assume this was our link list & there was a cycle present here Ok? And slow & fast pointer met at this point and suppose that this distance is 'A' This part is 'A' and the distance from here to here this distance is 'B' and this distance is 'C' this is the point where slow & fast pointer meets right? so if we say that, how much distance the slow pointer travelled? Distance traveled by Slow pointer & Distance traveled by fast pointer so we can say that they are relative to each other that Distance travelled by slow pointer multiplied by 2 is equal to distance travelled by fast pointer they are meeting at the same time but the slow pointer is moving slowly so it has traveled less distance Fast pointer is moving twice its speed so, Fast pointer has traveled twice the distance of the slow one So we can say that distance traveled by slow multiplied by 2 equals to distance traveled by fast Is it clear now? Now let's see what is the distance traveled by the slow one How much distance the slow one would have covered? We can say that Slow one has traveled 'A' Slow pointer traveled 'A' distance & then suppose Slow circled around in the cycle a few times before meeting Let's suppose it circled for 'M' times So, completing a circle means B + C It circled for 'M' times and then, it met at B point So this is our distance for Slow pointer.

And now if we multiply it with 2 Then this is equal to the distance traveled by the Fast pointer. Distance for the Fast one is 'A' Then suppose Fast one circled for 'N' times So, N ( B + C) + B So, slow one traveled this much distance and fast one traveled this much. If we multiply slow's distance by 2, it will be equal to distance by Fast one Suppose, Slow must have circled for 'M' times and Fast must have circled for 'N' times. OK Now let's try to find some relation between the two So, from this equation, we get that A + B = (N-M) (B+C) You can see, that B+C is this loop and, n-m because we are assuming that N is the fast pointer that, the fast pointer circled for 'N' times and the Slow pointer circled for 'M' times So obviously, the fast pointer will circle for more compared to the slow pointer that is why N should be greater than M And we can say that A+B is the interior multiple of N+M let's suppose this is lambda then we can say that this is lambda times B+C This is lambda times B+C and B+C is nothing but this cycle.

So we can also see the relation between A and C suppose lambda is 1 If lambda is 1, then we can say that A+B is equal to B+C Or we can say that A is equal to C So you can see that A is equal to C This is true when lambda is 1 So, all you need to do is place one pointer here and one here because both the distance is the same so they should match They both should match at this point But let's suppose that is not the case Suppose lambda is not equal to 1 lambda is something else Suppose lambda is 2 instead of 1 So, if lambda is equal to 2, then A+B = 2 times B+C And now your A will be equal to (B+C)+C (B + C) + C This means that here also A and C are equal But we have B+C, which is nothing but the cycle So we can say that this means Still, if I start one pointer from here and one pointer from here then, my pointers will meet here but only after finishing the circle once A is equal to B plus C, which means one circle plus C, right? So after the circle, they will definitely meet here that is guaranteed.

A equals to C plus B+C If lambda was 3 then, it would be 2 times B+C plus C which means they would circle twice but after that, they would meet at this point So it was a very simple proof you must have understood it Lets code it, you can also try it yourself The code is going to be very simple You must have understood the proof I have coded both the function First function is Detect Cycle It tells us if there is a cycle present in it or not. And how does it work if it shows a not null node, it means that the cycle is present if it shows null that means there is no cycle present The second function I have created, detect the first node this tells us the node from which the cycle is starting. So if this was the link list, then this is the node from where the cycle starts.

So this function will point us to this node Let's see how both of them works We already saw the proof for the both So we have coded the same So the first one which is detect cycle is that we make 2 pointers, slow and fast Move Slow pointer 1 step & Fast pointer 2 steps at a time and if both of them meets, it means that the cycle is present and you can return the intersection point but if the fast pointer show null, it means there is no cycle present So I did the same that while Fast is not null and fast dot next is not null move slow one step forward & fast 2 steps forward and if slow & fast meets then return slow otherwise, if they never meet & Fast is null then return null so if you try it here, then it will be your slow & fast will be at the same point here we will move them forward So, slow will be at the next node & fast will be on the next to next one slow will be here & fast will be here in the next iteration, slow will move one more step forward and fast will move 2 steps ahead so fast will reach here from there then again slow will move 1 step forward so it will be here fast will move two steps forward here In the next iteration, again Slow will move 1 step forward means the slow pointer will be here and fast will move 2 steps so it will be here so as you can see, slow & fast have met at this point and as soon as the slow & fast meet, you return slow means you return the node at this point this proves that yes a cycle exists here.

Now we have to find the node from where the cycle starts so, detect first node How will we detect the first node? so first of all we made the function with detect cycle and it gave us the pointer at this node lets call it meet this is our meet pointer and this pointer is start lets call it start and we have already seen the proof that if we will move start & meet by 1 step then it is guaranteed that they will meet at the intersection point. so while start is not equals to meet we will move both of them one step forward start = start dot next and meet = meet dot next you can try if we move start 1 step forward then it will be here and meet will come here from there next, start will be at this point and meet will also be at this point right? so start & meet both intersect at this point and as soon as they meet it will break the loop and and we will return start and we will return this pointer so your detect 1st node & detect cycle is working sometimes, the question arises that after detecting How to delete the cycle right? So there is a cycle within the link list & we have to delete it So all you have to do to delete the cycle is so now we have the pointer at this node if you can find the pointer to the node previous to it so all you have to do is, make the next of that node, null if you made the next of the node null then there will be no cycle so you have the pointer for this node but you have to find the pointer for this node to find the pointer for this node is also very easy you just have to maintain the previous one here if you maintained the previous then Previous one will always be just before meet if you achieve this, then you will make the next of the previous node null and the cycle will be deleted so I leave that upto you now.

it is very simple the entire code is mentioned in the description Also, I will give you some more problems to practice on in the description with that let's end this video do like this video and subscribe to the channel See you in the next video. Bye.