Detect a loop in a linked list

hi guys this is Malaysian from my desert today let us look at the problem of detecting the start of the loop in a linked list will solve this problem in order of n time complexity let us look at an example to understand this problem say we are given this linked list as you can see there is a loop in this linked list which starts at node 2 so the problem statement is if we are given this linked list we have to return the pointer to the highlighted node which basically is the start of the loop the approach to solve this problem is basically a two-step approach in the first step we take the loop in the linked list once we detect the presence of loop in the linked list in the second step we detect the start of that loop let us now look at the first step of this approach that is detecting the loop in the linked list we are going to use this algorithm in this algorithm the first step is we basically initialize two pointers a slow pointer s and fast pointer F to start off the list a slow pointer s and fast pointer F are initialized to start off the list in the second step what we do is we move pointer s one node at a time and we move pointer F two nodes at a time and while advancing pointer s and pointer F in step two if at some point these pointers point to same node then we say that there is loop in the list otherwise we say there is no loop let us try to visualize this algorithm for more clarity in the first step we have initialized both pointers s and F to start off the list we add once s by one node and F by two nodes until they meet or F reaches end of the list if F reaches end of the list then we know that there is no loop in the linked list so what we do is we advance s by one node and F by two nodes we check if s and F are pointing to same node they are not and F also has not reached the end of the list we again advance s by one node and F by two nodes they are not pointing to the same node we repeat this step now s points to 4 and F point to 7 we repeat this step here again they are not pointing to the same node we again repeat this step now at this point both s and F pointers are pointing to same node 3 and therefore we say that there a loop in this linked list please note that if there would not have been any loop in the linked list then f would reach the end of the linked list before meeting s in that case we say that there is no loop so we have used this algorithm to detect the loop having detected the loop in the linked list let us now see how we can detect the start of the loop that would be node to the first step to detect the start of the loop is we move as to the start of the list so s is now pointing to node 8 which is start of the list the second step of this algorithm is remove pointers s and F forward one node at a time until they meet note that pointer F is also moved forward one node at a time and not two nodes at a time we repeat step number two until pointers s and F meet let's try to visualize step number two now so s and F both are incremented by one node are they pointing to same node no so we again repeat step number two are they pointing to same node no so we again increment them by one node we check if they are pointing to same node no therefore what we do is we again increment them by one node here at this point they are now pointing to same node if you notice s and both s and F pointers are pointing to the start of the loop that is precisely our third step the node where they meet is the start of the loop just to quickly recap this algorithm what we did is after we detected the start of the loop we moved as to the start of the list and then we move s and F forward one node at a time until they met and at the point where they meet we say that that is the start of the loop now you must be thinking as to why this algorithm work let us try to see why exactly this algorithm works let L be the length of the loop will measure the distance in terms of number of links so in this case L would be five let M denote the distance of the start of the loop from beginning of the list so from node eight which is beginning of the list we measure the distance to node 2 which denotes the start of the loop so in this case M or before let K denote the distance of the meeting point of pointers slf from start of the loo when they met for the first time while we detected the loop remember that while we are detecting the loo s and F met at node 3 therefore K would be 1 because it measures distance from the start of the loop to the meeting point so having defined this L AM and K let's say when s and F meet for the first time discussed our bias is M plus PL plus K M because it has to enter the start of the loop then let's say it completed P rounds of this loop so that is PL and it made pointer F at distance K from the start of the loop a distance K from the start of the loop therefore total distance traveled by s when it met F is M plus PL plus K similarly total distance traveled by F when it met as for the first time would be M plus QL plus K also note that Q would be greater than P because f travels faster than s now recall that when s and F met for the first time while detecting the loop they were pointing to node3 in the list we also know that f traveled twice as fast as s when they met for the first time therefore distance covered by f would be 2 times distance covered by s or 2 into M plus PA plus K would be equal to M plus QL plus K solving this equation we get M plus K equal to Q minus 2 P into L which implies that M plus K is integer multiple of length of the loop if length of the loop is L then M plus K is integer multiple of length of the loop now recall the algorithm that we use after assigned F meant for the first time what we did is we moved back s to the start of the loop so s is moved back to the start of the loop f is kept at the same meeting point that is it is pointing to node 3 and s is pointing to node a it and then in the second step we move both s and F forward one node at a time until they met now note that when this pointer has reaches the start of the loop that is no - it would have covered distance of M links now when we are moving this pointer else we are also moving this pointer F forward one node at a time therefore when this s covers distance of M links from start of the loop that would have also covered distance of M links from this position right now recall that F was placed at the point which is a distance K from the start of the loop therefore when it travels M links it is a distance M plus K links from the start of the loop this K denotes the offset of the pointer F from the start of the loop when it started moving when s covers distance of M from the start F also covers distance of M but it was placed that distance K from the start of the loop therefore in all it has traveled M plus K links from the start of the loop and M plus K is integer multiple of length of the loop therefore we can say that F must have reached the start of the loop when s has covered M or when s has reached start of the loop so the meeting point of s and F must be start of the loop hopefully the explanation of why this algorithm works is clear now once you understand this algorithm implementing this algorithm in code history L please let us know in the comment section if you have any queries or feedback please do not forget to like comment and share this video thank you and Cheers

Channel: IDeserve

Views: 43,200

Keywords: Detect a loop in Linked List, find the start of loop in a linked list, find loop in linked list java, floyd's cycle-finding algorithm, tortoise and hare algorithm, floyd's cycle-finding algorithm java, floyd's cycle-finding algorithm proof, floyd's cycle-finding algorithm linked list, floyd's algorithm

Id: apIw0Opq5nk

Length: 7min 53sec (473 seconds)

Published: Wed Sep 02 2015