Detecting a Loop in Singly Linked List - Tortoise & Hare

This article is part of article series - "Datastructures"

Previous Article: Reversing a Singly Linked List.
Next Article: Finding first node in a Loop in Singly Linked List.

Eventhough there are multiple algorithms available we start with

Floyd's Cycle-Finding Algorithm
In simple terms it is also known as "Tortoise and Hare Algorithm" or "Floyd's Cycle Detection Algorithm" named after its inventor Robert Floyd. It is one of the simple cycle detection algorithm. It's a simple pointers based approach.

Robert Floyd

Let us take 2 pointers namely slow Pointer and fast Pointer to traverse a Singly Linked List at different speeds. A slow Pointer (Also called Tortoise) moves one step forward while fast Pointer (Also called Hare) moves 2 steps forward

1. Start Tortoise and Hare at the first node of the List.
2. If Hare reaches end of the List, return as there is no loop in the list.
3. Else move Hare one step forward.
4. If Hare reaches end of the List, return as there is no loop in the list.
5. Else move Hare and Tortoise one step forward.
6. If Hare and Tortoise pointing to same Node return, we found loop in the List.
7. Else start with STEP-2.

Pseudocode:

tortoise := firstNode
hare := firstNode

forever:

  if hare == end 
    return 'No Loop Found'

  hare := hare.next

  if hare == end
    return 'No Loop Found'

  hare = hare.next
  tortoise = tortoise.next

  if hare == tortoise
    return 'Loop Found'

Why can't we let the Hare go by itself like Tortoise ?
If there is a loop, Hare would just go forever. Tortoise ensures that you will only take 'n' steps atmost.

How to find the length of the Loop ?
Once Hare and Tortoise finds the loop in a Singly linked List move Tortoise one step forward everytime maintaining the count of the nodes until it reaches the Hare again.

Example:

Singly Linked List with a Loop

Both Tortoise and Hare starts at First node of the list and Tortoise moves 1 step forward while Hare moves 2 steps forward.

Hare and Tortoise starts at First Node of the List

The pattern of Hare and Tortoise movements are shown below.

Hare   Tortoise
1          1
3          2
5          3
7          4
3          5
5          6
7          7

Both Hare and Tortoise meet up at Node 7. That proves there is a loop in the list

Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

To calculate the Time Complexity 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 can never catch up with the Hare. If the two has to meet, the Hare has to catch up with the Tortoise from behind.

With that established, consider the two possibilities

• Hare is one step behind Tortoise
• Hare is two step behind Tortoise

All greater distances will reduce to One or Two. Let us assume always Tortoise moves first  (it could be even other way).

In the first case were the distance between Hare and Tortoise is one step. Tortoise moves one step forward and the distance between Hare and Tortoise becomes 2. Now Hare moves 2 steps forward meeting up with Tortoise.

In the second case were the distance between Hare and Tortoise is two steps. Tortoise moves one step forward and the distance between Hare and Tortoise becomes 3. Now Hare moved 2 steps forward which makes the distance between Hare and Tortoise as 1. It is similar to first case which we already proved that both Hare and Tortoise will meet up in next step.

Let the length of the loop be 'n' and there are 'p' variables before the loop. Hare traverses the loop twice in 'n' moves, they are guaranteed to meet in O(n).


Previous Article: Reversing a Singly Linked List.
Next Article: Finding first node in a Loop in Singly Linked List.