'Cycle detection in linked list with the Hare and Tortoise approach

I understand that in order to detect a cycle in a linked list I can use the Hare and Tortoise approach, which holds 2 pointers (slow and fast ones). However, after reading in wiki and other resources, I do not understand why is it guaranteed that the two pointers will meet in O(n) time complexity.

algorithmlinked-listdetectioncyclefloyd-cycle-finding


Solution 1:[1]

Let iterators A and B go through the list respectively by ones and by twos. Consdier there exists a loop. Then at the moment when A enters the loop, B will already be somewhere inside it. If the length of the loop is K, then B will run around it in ]K/2[ moves, so at most in 2*]K/2[ iterations we will get a situation when B appears behind A in a distance 1: B->A or 2: B->.->A, and it's B'th turn. After this, obviously, they will meet either in 1 or 2 moves. So, if the loop exists and begins at some position P, then we do at most 2*P + 2*]K/2[ + 2 = O(N) iterations.

Solution 2:[2]

this is the while loop of tortoise and hare algorithm:

    while tortoise:
        hare = hare.next
        tortoise = tortoise.next
        # if not hare, states that i have a single node.
        # hare.next means that we have a tail value. So we do not have a cycle
        if (not hare) or (not hare.next):
            return False
        else:
            hare = hare.next
        if tortoise == hare:
            return True

Although hare moves 2 steps forward, meaning that there is a chance that it might loop over and over again within the cycle, and touch multiple nodes over and over again, technically speaking, it is all happening within one while loop.

Solution 3:[3]

//if you just want to check if there is a loop

loop = false;
item = head-of-list; 
while (item != nil)
{
   if (item.next < 0) 
   {
      loop = true; 
      break; 
   }
   else
   {
      actual = item;
      item = item.next; 
      actual.next = actual.next * -1; 
   }
} 

return loop;

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 Grigor Gevorgyan
Solution 2 Yilmaz
Solution 3 Nunser

Related Questions