Why Floyd's cycle detection algorithm works? Detecting loop in a linked list.
Vložit
- čas přidán 23. 06. 2017
- Why Floyd's cycle detection algorithm works? Detecting loop in a linked list. You have to check whether there is a cycle in a linked list and find out the starting node of the cycle or the loop. You can also find out the length of the loop. Also known as Tortoise and Hare algorithm.
Detect loop in linked list :- • Detect loop in linked ...
This guy should be a youtube celebrity! People like him who share knowledge should be made famous.
can't agree more, very well explanation!
he is a celebrity already
Must be
I guess one minor point that I couldn't find in his video is this:
(m+k) = integer*l -> this means, if you have p at the kth node and q at the start, by the time q travels m+k nodes from the start, p will finish one complete revolution on that loop.
i.e., p and q will coincide at the kth node again.
But if q only travels m nodes, p has travelled only (integer*l)- k nodes as well. So if p started at the kth node, and q at the start, they will meet at the start of the loop.
(I hope this makes sense as it does in my head lol)
Thanks for the video Vivek!
``But if q only travels m nodes, p has travelled only (integer*l)- k nodes as well. So if p started at the kth node, and q at the start, they will meet at the start of the loop.``
can you explain this part again please, this is not clear to me,
@@vaibhavrbs p has already made k steps from the start of loop so to reach the start point again, it should travel (int * l) - k. it equals that q will make only m steps to reach the start point.
other words, we had equation: m + k = int * l and then we subtract k from both sides. equation is still correct, now q will make m steps to reach the start point and at this place it will meet p. (p made (int*l)-k steps)
You are absolutely right. Something was missing in that video but THAT"s the main point!
Honestly think THIS should be the main focus, thanks for pointing out
You missed one minor key point as well, ASSUMING q is equal to p after q starts from 0 and p starts from k, and *your rest of the logic*.
OMG! This is the 1st video I am watching of this person and I am in love with his way of explaining things!
I hope the rest of his videos are equally good.
I can now recollect some friend recommending this person's videos.
@Vivekanand ...You definitely have a fan base!
worth spending 24 minutes , good work.
I really enjoy your videos and your videos are helping a lot of people as we. I recommended your channel to many of my colleague and college friends. Keep up the good work. ;)
Good to see you after a long time! Great work.
Good going!! :)
Hi Vivekanand sir, can't thank you enough for making this video. I have seen almost half a dozen videos on this online and after this I can understand the logic behind it fully. Worth spending 24 minutes. Kudos to you!
Your videos are really helpful. Thanks a lot for making them :)
after a couple rewinds, i finally got it. i doubt i could ever come up with this algorithm on my own. good vid
Your explanation is so good that makes learning easy. Great work my friend!
You really save me from struggling with the textbooks and any other recourses I could find, thanks !
Finally, there's a video that helps me understand this algorithm. Thanks a lot!
Thank you so much
I like the way you explained this. Thank you a lot)
Wonderful explanation - thank you very much.
Thank you. i was struggling with this since long.
Awesome explanation! Thanks 🙏
Thanks for such a Nice Explanation.
this man is unbelievable , the way he explains is just mind blowing
doing good job!! excellent work keep them coming !!!
Thanks Anand..!
Thanks, mann! Finally understood this concept clearly!
Wow, excellent explanation dude! I was trying to figure out why this algorithm worked, and finally I found the right answer. Keep going this videos!
I am convinced that I understood the explanation. Thank you!
this was great, thank you!
Thank you for wonderful explanation
Very nice explanation!
This is awesome, this really helped me to finally understand it, thank you.
Excellent explanation!
Excellent explanation !!!
Very well explained.
Wow man this was just amazing, thanks a ton!
Great Job !!! Crystal clear explanation !!
WOW, very very VERY good explanations, thank u for these videos !!!!!!!!!!!!
thanks for explaining it so well..
Thanks. Nice explanation
you are seriously amazing bro...i love your knowledge and teaching way, keep up the good work..
Very clear explanation!
Your Explanation is amazing Sir!! Keep making videos
That was beautiful and made me happy thank you so much
Very Nice Explanation
very well explanation!
Thanks, it is the best explanation I have seen so far
OMG - Such a beautiful explanation! I'm listening to Vivek Sir's video first time. I'm sure, I'm in for a treat when I will search for other videos of his teaching. Stay blessed Sir.
Great explaination thank you
Such wonderful explanation.Very helpful.
Thank you so much for this video.
Clear explanation! Thanks!
Great simplified explanations.
Thanks for the explanation!
Excellent video !!
Thank You sir!
This is very clear and detailed, thanks a lot.
really helpful... Thanks a lot
Really excellent explanation - thank you
Thanks a lot! I was struggling to understand this at first!
One Point to mention.!!
Rather than saying that Distance of P traveled would be Double the Distance of Q because "P's speed is twice than that of Q" kind of makes it incorrect statement. What we can explain is
Let's say they start their journey at time T = 0. Now when they meet the time elapsed would be equal (Why? Because the time frame is absolute. Doesn't matter how they move they will meet only when they are in the same position at the SAME TIME)
So, we know S = D/T (Speed = Distance/Time which also means T = D/S), from the equation we can say
Tp (Time taken for P to reach the meeting point) = Tq ( Time taken for Q to reach the meeting point)
or
(m + pl + k)/2 = (m+ql+k)/1
Now work up to get, ---> (m+k) = l * (p-2q)
NOTE: Another thing worth noting is that (2q-p) is also an integer but it'll never take the form of (2q-p) (Why? Because the left-hand side has a dimension of length (scalar) and hence cannot be negative).. Now, why is that (2q-p) is likely to be negative? Because P's speed is greater than Q. So its likely that P would travel the loop more number of times than Q will
Hence,
p > q/2 --> (Why q/2 ? follows from the above discussion)
Or, (p - 2q) > 0 but (q-2p) < 0
It was just a suggestion!. The explanation is wonderful. It's just a part where I felt needed a little bit more clarification
your teaching style is amazing ! i dont know why u dont have million subs
it finally became clear! thanks a lot!
Thanks, this is very detailed.
Thanks! YOU make my day
Best explanation I've seen so far!
Thank you!
Thank you very much Sir.. It was very helpful :)
very well explained thank you..............................
Hi,
I have no knowledge about algo, but i do have a question.
in detecting the start of the loop, what happens if Q started at say, a different index than stated?
P will not equal Q throughout the loop.
Thank you sir ..... Great explanation ....
This was awesome 👍
nice explannation.Thanks
Thanks a lot! It really helps ;)
Awesome explanation Sir : )
Thank you , keep continue
Excellent!
I got same confusion after seen the solution on leetcode. How they meet eachother at the beginning of the cycle but now it is clear. Thanks Viveka you are great...
I didn't see such a clr explanation ever .... keep going sir
Thank You very much.
Bestest explaination ever!
very nice explanation
Brilliant Explanation in simple words.....
Thanks Chakrapani.!
Wow! Thanks.
Thanks sir
Thanks man, this is way more clear than the leetcode answer
heroic explanation
Thanks Sir
You make it understand in very simple way
You are very good, I am english but find your videos far clearer than any native english speaker's video's. How do you gain the knowledge of these algorithms ? do you have a book ? I purchased 'introduction to algorithms' but find it very technical and hard to understand.
Honestly, I think its just going through this book called CLRS and preparing by just looking at more and more problems and how to solve them
If you go to leetcode.com and start solving I'm sure you will start to get an intuition
Also, these are algorithms that are used and proved. Its a lot about just learning these.
geeksforgeeks is a good resource too.
Thanks sir ek no!!💯💯
What a explanation!!!
Nice explanation ...
How will the slow pointer traverse the cycle multiple times?
The distance for slow pointer should be m+k right? Since the slow pointer won't traverse the loop again.
Nice explanation
THANK YOU!
thank you, sir, you explained such a confusing concept very well! :)
Just awesome😊
Great explanation sir I salute you it's help me allot
1. Best explanation I've found to describe this! No other explanation made sense.
2. I love the way you say "loop" XD.
Very clear and concise explanation. Nice work.
kyaa bataya hain aaapne jo koi na samgha saka aapne samgha diya bohot sahi
Understood well
thank you
clear explanation :D!!
You are awesome!!!