# Loop detection in Singly Linked List.

**Floyd’s Cycle Detection Algorithm (The Tortoise and the Hare) :**

**In Brief : ** How do you determine if your singly-linked list has a cycle?

In the late 1960s, Robert W. Floyd invented an algorithm that worked in linear **(O(N))** time. It is also called **Floyd’s cycle detection algorithm** or **The Tortoise and the Hare**

The easiest solution to the cycle detection problem is to run through the list, keeping track of which nodes you visit, and on each node check to see if it is the same as any of the previous nodes. It’s pretty obvious that this runs in quadratic (O(N^2)) time… not very efficient, and actually more complicated than this one.

The Tortoise and the Hare is possibly the most famous cycle detection algorithm, and is surprisingly straightforward. The Tortoise and the Hare are both pointers, and both start at the top of the list. For each iteration…

View original post 105 more words

Posted on June 27, 2013, in Algorithms, Data Structures and tagged Floyd's cycle detection algorithm, Loop detection in Singly Linked List, The Tortoise and the Hare. Bookmark the permalink. Leave a comment.

## Leave a comment

## Comments 0