hey i have an alternate solution for finding head. after hare and tortoise meet. we will make hare pointer stop at that point and make tortoise pointer move till it reaches hare pointer again and count number on nodes. this will give us length of cycle. ( how many nodes are in cycle). lets denote dis with c. then just take 2 pointers p1 and p2 at c distance apart.. and move both at SAME speed till p1 and p2 meets. that point will be head.

in the end, he meant we get to the Starting point in the cycle since, Moving a Pointer from Head 'D' times = moving the pointer from the meeting point in cycle some constants times - K node Hence the solution works. Thanks, Gaurav this was really helpful.

If you get asked this question in an interview and instantly respond with Tortoise and Hare you’ll likely get another question. I think some people forget the goal of interviews questions is often to see how you solve a problem you don’t already know... that being said, this is one of the better explanations I’ve seen for this algo

Bro, I searched the whole internet to get the proof which I could understand. I wasted my two days in that search and couldn't find one which made sense to me or which I can sink the proof in. I watched your video twice. And I could finally sink it in. Thank you so much man! you saved me. Especially the last proof of how to make the pointers point to the starting node.

You're not only good at the CS part of things, you're also an amazing teacher! I kept asking a question in my head only to have you answer it right after. Thank you for this amazing lesson!

Thank god, finally someone explained the intuition behind this.. You're just amazing 🙌

It was hard wrap my head around this concept. Thank you for making this video and providing with a detailed explanation.

most important thing is how to act like you have seen this question for first time in an interview :))

Love the energy of your teaching style!

Keep up the stellar work! This is some really useful stuff!!

it is evident that he kept trying to understand why it works for a long time and then finally when he understood he was so happy❤

Awesome video! Thank you for explaining so clearly

Was stuck at this problem over a month, now i finally understand it, thanks a lot!!!

Thank you, this is a new concept to me

That was a great explanation. Thx so much for the help! :-)

Loved this explanation, finally I fully understand how it works💡

Gaurav maaaan! I saw this question a few years back And couldn't understand the solution. This video helped! 😄. Thanks

oh man, you are something else, fantastic explanation!!!

Cool !! That was a great explanation.

Thanks a lot, this video was really helpful!!

Finally someone explaining the math, thanks!

Great explanation!!

Hi Gaurav ,You nicely explained the explained the existance of solution for the equation but it can also be explained by the fact that if loop exist ,then when tortoise enter into the loop there are two particle in loop moving with different angular speed. So they have to meet at point. Relative angular speed is non zero constant so they must collide.

Exactly the explanation I wanted to know.

So,this was a interesting questions. I found a solution after couple of years.😁 At last excellent explaination.

watching it in 2020... deeply explained. thanks !

FINALLY GOT IT! THANKS

after watching it 3 times finally got it, now i can also explain it someone

Great explanation, love the intuition you give !!! Amazing content, love your channel. I will share this video with my Junior college-mates :)

...15 years ago it took me couple of hours to find this solution, though after some fiddling with analytical approach which was hard to interpret, finished with much easier graphical...

Freakin awesome man ! thank you !

I got it! Very clear. Thank you!

Coming here after going through two different sources , now I don't need to go any where because solution make sense to me now :) . Thanks for your efforts!!

Well explained! I didn't understand even though I read the solution but I totally got it with your video. Thank you :)

Thanks a lot. This video help me understand the logic behind this.

Your explanation deserves an extra like! Great video bro

Awesome Explanation !!

Great explanation with the equations

Excellent Explanation. Keep up the good work man...!

start with fast and slow pointers. When slow meets fast, stop. Take a pointer p1, now assign head to p1. Move p1 by one position and slow by one position till p1 and slow meet. By the way, slow and p1 will meet exactly at the start of the loop.

Man this is wonderful, I was so stuck in this problem, went through multiple videos but finally found the perfect explanation. Thanks a ton, Gaurav.

thankyou for this much needed explanation.

Thank you for this video

very well explained!

The -K part really hits the point! Nice work!

Great video. Thanks for sharing!

Beautiful Explanation Brother !!!

Very good explanation. Thanks!

Such a nice explanation D+K part was explained so nicely, thanks bhaiya

Watch it twice to get the intuition :')

awesome explanation !!

9:00 this was the missing link I was looking for! Thanks Gaurav bhai for this explanation!!!

Your explanation proves that from the meeting point i.e. c(j - 2i) it falls 'k' short to reach the intersection point, but it doesn't prove that from the meeting point it will take 'D' to reach the intersection point. I think what is missing over here is you will have to prove 'j-2i' is always equal to 1.

U are really good at explaining things :)

atlast someone explained the algorithm with proof. amazing work.

Thank you so much! Your explanation is excellent! Really helps me a lot understanding the question!

Thanks for the mathematical proof but test case which includes a whole circular linked list requires slight change in finding the start of the loop ie. head

How do you compare nodes in a cyclic graph though? In the final solution it seems like you need to start a pointer at the head (hptr) and at the meeting point (mptr), move forward by 1 and then check if hptr == mptr. how would the linked list implementation handle that? memory location or following the nodes?

thanks for explanation 😃

The first question they ask in any damn interview.

great work man. Keep doing. 👍👍👍👍👍👍👍

Excellent explanation

Thank You Sir.

great explanation

finally understood the logic thanks

When ever we are choosing the slow pointer and fast pointer how fast they should move(can slow pointer move twice and fast pointer move three times .How we should decide.)

Thanks buddy!

No need to add maths equations too. Consider a very large cycle so that the first pointer when it reaches the starting node of the cycle is t distance behind the fast pointer. That means that fast pointer is (c-t) distance behind the first to catch up with it. So, we have (c-t) + y = 2y assuming at y nodes far away the both will meet. so y = (c-t) or in other words, the meeting point is at distance c from the head pointer. So now just take head and slow pointer(at the meeting point) and keep doing ->next until they both coincide. That will be the answer.

Hi Gaurav, Nice explanation. But you needed to say that k=(j-2i)x-D, so the slow pointer is at D iterations short of a cycle. So just by iterating it D number of time, we can get to the beginning

Could someone please point me to the link of an implementation for this

Well explained :)

If space complexity is not an issue, we can iterate the loop till it reaches null and keep checking each node in HashSet. If a node doesn't exist then add it to HashSet and if it exists then break the loop and return that node which is the start of loop. To find length of the loop, we can keep extra Stack where we push the node while iterating until we discover the starting node of the loop as mentioned above. Then keep popping the nodes from the stack until we get the starting node and keep a counter while popping which is the length of the loop.

WOW, Thanks Gaurav

Thanks man

Gotcha! I had to re-watch, but got it finally.

great explanation. Written explanations out there are hard to understand. nice job!

i didnt understand what there is fallshort ?

Thanks a lot Gaurav Bhai

Nicely Explained! :)

Don't you think the distance k should represent distance from 2 to 4 instead of 3 to 4? Otherwise, the equation itself will not be right. Moreover, when you say, in the end, that we would be 'k' short that means from the meeting point we would go back to 3 not 2, correct?

Awesome explanation Gaurav!

Thank you Gaurav.

Awesome!

Thanks !!

I would have known the solution posted by @shlok singh But your solution is smarter and shorter. I will keep this in mind.

Best Explanation. Thanks Gaurav for this. 1) At the meeting point one pointer that starts from start covers D. 2) Now at the same point when the next pointer start from meeting point trying to travel D, It will cover N*(circle Length) - k. so from the point it started at will be k steps before. And k steps before is actually the meeting point. So they both will meet at the meeting point.

Great Explanation Sir

nice explanation bro.

If we start the pointer at the start and one at the meeting point and move them by D+K then both end up at the same place? Can you be more specific around 8:05 to 8:12

We can explain it even simpler if we set the starting of loop at the head node( the starting node). And then make it complex by adding the nodes at the starting point.

very nice explanation tank you

At around 3:45 why does n need the c and i variables? Doesn't the tortoise never make it through a full cycle since the hair would intersect it before that happens?

Thank u gaurav ...👍

Hey Gaurav, let's say that if the question asked was to find out start point of the loop. How is this algorithm efficient than hashing? hashing would always take O(N) space and run time is O(N). but this algorithm runtime can be more than O(N).. but I agree that this will always take a constant space O(1). Just trying to understanding which one is better?

the equation that you figured out at 4:36 th sec that is N=C*(j-i). Does it mean that walking for some value of N (where n is D+K+C(i)) steps is same as making few complete cyclic loops ?

whats time complexity of this solution?

Nice explanation and logic deduction Gaurav_Sen..!!

Hi Gaurav, Alternative code for finding the starting node of linked list cycle. Please let me know if there are any issues. if (loopExist) { slwPtr = slwPtr.next; List list = new ArrayList(); while (slwPtr != fstPtr) { list.add(slwPtr); slwPtr = slwPtr.next; } slwPtr = head; while (slwPtr != fstPtr) { if (list.contains(slwPtr)) { return slwPtr; } slwPtr = slwPtr.next; } } start = slwPtr; return start;

nice explaination

I have a question. How are we going to compute the length D? Because if we dont we cannot stop the pointer P1.