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.
-
This is the tortoise and hare detection method.willeM_ Van Onsem– willeM_ Van Onsem2016-06-06 07:29:21 +00:00Commented Jun 6, 2016 at 7:29
-
3There 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.willeM_ Van Onsem– willeM_ Van Onsem2016-06-06 07:35:44 +00:00Commented Jun 6, 2016 at 7:35
Add a comment
|
2 Answers
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.
Comments
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:
- slow = index 0; fast = index 0
- slow = index 1; fast = index 2
- slow = index 2; fast = index 1
- slow = index 3; fast = index 3 (loop exists)
Hope this helps!
1 Comment
Rishabh Mamgain
Still cant find a mathematical proof behind it.