Linked list loop detection

Question

how we can prove that moving fast and slow pointer(from the begining) by 1 makes there meeting point the loop node?I mean i cant understand what gives it a guranteed solution that the meeting node is the loop node(i.e node from where cycle starts)
I am clear with tortoise hare loop detection basically i am talking about detcting the node where cycle starts after loop has been detected.

• willeM_ Van Onsem: This is the tortoise and hare detection method.
• willeM_ Van Onsem: There is no guarantee - as far as I know - that you will meet in the node where the cycle starts. The tortoise and hare method however guarantees that you will meet in a node that is part of the loop.

Answer 1

It's a very simple proof really. First, you proof that the slow pointer will match the fast pointer after at most n + k steps, where n is the number of links to the start of the cycle, and k is the length of the cycle. And then you proof that they will match again after exactly k further steps.

The point where they meet will be anywhere in the cycle.

Answer 2

Before trying to prove this formally, you should first look at an example so you can get a more intuitive understanding of, and can visualize, what is going on. Suppose you have the following linked list, in which the 3 (at index 3) points back to the 1 (at index 1):

[0| ]->[1| ]->[2| ]->[3| ]--+
 ^ |
 | |
 | |
 +------------------+

Walking through the logical progression, you can observe the following when incrementing slow by one position and fast by two:

1. slow = index 0; fast = index 0
2. slow = index 1; fast = index 2
3. slow = index 2; fast = index 1
4. slow = index 3; fast = index 3 (loop exists)

Hope this helps!

• Rishabh Mamgain: Still cant find a mathematical proof behind it.