69 CS651 Lecture Notes - Lecture 36: Cycle Detection, Lookup Table, Linked List
1 Mar 2023
Department
Course
Professor
L36: HOW TO DETECT A LOOP In A Linked List In
Java | Lesson 36 | DSA In Java | @CodingNinjasIndia
Coding Ninjas
In this video, we'll look at how to detect a loop in a linked list. then We'll see an
optimized algorithm that is known as the Floyd cycle detection algorithm, also
known as Hair and Tortoise algorithm. finally, we 'll code the algorithm and
submit it on code studio. This video is part of a new playlist that is data
structures algorithms in Java by coding ninjas. If we are revisiting any node, then
we say that there exists a loop in a linkage so what we can do is. We can
maintain a lookup table or which can be in the form of an array. each index of
the array denotes whether we have visited that UH value or not. So let me show
what I mean. linklish is a linklish which is which does not have a loop, so I hope
the upload is clear but this approach. is fine like the time complexity here would
be big O of n, which because we are only traversing all the nodes. Where N
defines the number of the nodes. So therefore big off. the space complexity is
dependent upon the maximum value in the linked list. As we saw that I had only
three nodes, but one of the node had a value of 10. So I had to make the visited
array of size 11 basically 10 plus 1. So we can say 11..
Data section regardless of Java by coding ninjas. In this course you'll learn data
structure and algorithms in Java. in a structured way. Every course comes with
great doubt support through teaching assistants who will give you the attention
that you need. after which you will be able to crack any technical interview for
any company so check out the amazing code card is data section algorithm.
Java. the floyd cycle detection algorithm says that if the slow and fast pointer
meet at any moment in a linked list, then a loop exists. So there exists a loop
which basically is the algorithm. that these two pointers meet. the algorithm that
is the Floyd cycle detection algorithm is all about we set up two pointers, where
one pointer moves one node at a time and another pointer moves two nodes at
a. time.. we are only maintaining two pointers no. extra space, we are not using
any extra space so that 's why the time complexity is still big. O often why
because we are traversing all of the nodes, But now the space complexity is
reduced down to one big of one. we have eliminated extra space while
maintaining our time complexity, so it is upgraded optimization. So I really hope
you understood this algorithm and now we 'll look at how to remove the loop..
The distance from the start to the loop point of the node will always be equal to
some distance where the both of the slow and fast points are made to the
node... The final conclusion for this was that the distance from head to the the
loop node is equal to the distance. for the formal proof of this algorithm, you
can look at this amazing blog at coding Ninja slash blogs. if the both of the
Document Summary
L36: how to detect a loop in a linked list in. Java | lesson 36 | dsa in java | @codingninjasindia. This video is part of a new playlist that is data structures algorithms in java by coding ninjas. If we are revisiting an y node, then we say that there exists a loop in a linkage so what we can do is. We can maintain a lookup table or which can be in the form of an array. each index of the array denotes whether we have visited that uh value or not. Where n defines the number of the nodes. So therefore big off. the space complexity is dependent upon the maximum value in the linked list. As we saw that i had only three nodes, but one of the node had a value of 10. So i had to make the visited array of size 11 basically 10 plus 1.
