Cycle detection in linked list with the Hare and Tortoise approach

Question

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.

Lodged

Are you looking for a formal mathematical proof, or just an informal explanation ? – Interstadial

Formal (but easy to understand) proof. Check the second answer from top. #2936713 – Wellfixed

Answer 1

Here's an attempt at an informal proof.

The shape of the cycle doesn't matter. It can have a long tail, and a loop towards the end, or just a loop from the beginning to the end without a tail. Irrespective of the shape of the cycle, one thing is clear - that the tortoise pointer can not catch up to the hare pointer. If the two were ever to meet, the hare pointer has to catch up the to tortoise pointer from behind.

With that established, consider the two possibilites:

1. hare pointer is one step behind the tortoise pointer.
2. hare pointer is two steps behind the tortoise pointer.

All greater distances will reduce to one or two eventually.

Assuming the tortoise pointer always moves first (can be the other way around too), then in the first case, the tortoise pointer takes one step forward. Now the distance between them is 2. When the hare pointer takes 2 steps now, they will land on the same node. Here's the same thing illustrated for easier understanding. Too much text can get in the way.

♛ = hare
♙ = tortoise
X = both meet

..♛♙... #1 - Initially, the hare is one step behind the tortoise.
..♛.♙.. #2 - Now the tortoise takes one step. now hare is two steps behind.
....X.. #3 - Next, the hare takes two steps and they meet!

Now let's consider the second case where the distance between them is 2. The slow pointer moves one step forward and the distance between them becomes 3. Next, the fast pointer moves forward two steps and the distance between them reduces to 1 which is identical to the first case in which we have already proved that they will meet in one more step. Again, illustrated for easier understanding.

.♛.♙... #1 - Initially, the hare is two steps behind the tortoise.
.♛..♙.. #2 - Now the tortoise takes one step and they become three steps apart.
...♛♙.. #3 - Next, the hare takes two steps which is identical to previous case.

Now, as to why this algorithm is guaranteed to be in O(n), use what we've already established that the hare will meet the tortoise before it moves ahead. Which means that once both are inside the loop, before the tortoise completes another round, it will meet the hare since the hare moves twice as fast. In the worst case, the loop will be a circle with n nodes. While the tortoise can only complete one round in n steps, the hare can complete two rounds in that time. Even if the hare missed the tortoise in its first round (which it will), it's definitely going to catch up to the tortoise in its second round.

Tempered

Got it , thanks! So just want to make sure I completely get it - once the slow pointer gets into the loop (the fast one is obviously already in it), it is guaranteed that the first time the fast pointer tries to bypass the slow one, they will actually meet. – Lodged

Yep, absolutely, and since the fast pointer traverses the loop twice in n moves (considering the length of the loop is n), they are guaranteed to meet in O(n). Also to prove why we can't have a lower bound than O(n), consider the worst case where the entire list loops and looks like a circle. Both start at node 0. By the time the fast pointer finishes one loop, the slow pointer is already half-way across the list (n/2) steps. In another (n/2) steps, the fast will finish another iteration, and the slow one will finish the first iteration. – Tempered

Answer 2

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.

Lathan

Answer 3

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.

Chinkiang

Answer 4

//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; 

Mona