CODEWITHSUNDEEP
algorithmdata-structureslinked-list
Rishabh Mamgain
Rishabh Mamgain

Reputation: 23

Linked list loop detection

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.

Upvotes: 0

Views: 121

Answers (2)

user1585762
user1585762

Reputation: 79

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!

Upvotes: 1

gnasher729
gnasher729

Reputation: 52538

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.

Upvotes: 1

Related Questions