Skip to main content

Posts

Showing posts from June, 2019

Detecting starting point of loop in a linked list

Detecting the starting point of a loop in a linked list is a very popular problem. In fact most you reading this might already be knowing the algorithm to solve this. However understanding why that algorithm works is a separate challenge altogether. I was in the same state and decided to find an explanation of why it works. I could not find convincing explanations by simple google searches and hence decided to right this blog. Hopefully, this will satisfy the curiosity of people trying to understand the reasoning behind this algorithm. I believe coming up with this algorithm in the first place is an even bigger challenge. You will have to stay with this problem a lot longer if you want to do that. For now let's assume we have the algorithm and let's try to prove why it should work. The Algorithm The key insight of the algorithm is that we need to maintain two pointers: Slow and Fast, Slow pointer: Moves one node at a time. Fast pointer: Moves two nodes at a tim