**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 |

**Tortoise**) moves one step forward while fast Pointer (Also called

**Hare**) moves 2 steps forward

- Start
**Tortoise**and**Hare**at the first node of the List. - If
**Hare**reaches end of the List, return as there is no loop in the list. - Else move
**Hare**one step forward. - If
**Hare**reaches end of the List, return as there is no loop in the list. - Else move
**Hare**and**Tortoise**one step forward. - If
**Hare**and**Tortoise**pointing to same Node return, we found loop in the List. - 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

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.

I was asked this question in an interview last year, good write-up.

ReplyDeleteAlways nice to get a refresher on this question. Great analogy!

ReplyDeletePlease is it possible to Visual Basic 6 linked list soft. Thank you.

ReplyDeleteNice article. It really helped me. Thanks a lot :)

ReplyDeleteVery well explained, fast and slow pointers are more confusing than tortoise and hare.

ReplyDeleteNice explanation, Thanks :)

ReplyDeleteHow do we find the point where the loop starts?

ReplyDeleteAt the top of this article: http://codingfreak.blogspot.com/2012/12/detecting-first-node-in-a-loop.html

DeleteYou can determine the size of the cycle by iterating one pointer by one step until it meets again. Knowing the size, you can then walk backwards with the hare and test the tortoise until he no longer meets the hare.

ReplyDeleteNice Article

ReplyDeleteVery clear

ReplyDelete