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

 tortoise = top
 hare = top
  
 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'	

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, the Tortoise takes one step and the Hare takes two. If there is a loop, the hare will go around that loop (possibly more than once) and eventually meet up with the turtle when the turtle gets into the loop. If there is no loop, the hare will get to the end of the list without meeting up with the turtle.

Why can’t you just let the hare go by itself? If there was a loop, it would just go forever; the turtle ensues you will only take n steps at most.

Note : Most of the part of this post is taken from http://www.siafoo.net/algorithm/10

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s