ISourceCode

Make the frequent cases fast and the rare case correct

Floyd Cycle Detection Algorithm or “Tortoise and Hare Algorithm” for finding a loop in a Linked List.

Floyd’s cycle-finding algorithm, also called the “tortoise and the hare” algorithm, is a pointer algorithm that uses only two pointers, which move through the sequence at different speeds. The algorithm is named for Robert W. Floyd, who invented it in the late 1960s – Wikipedia

Created a Loop : 60->50->40->30->20->10->40

Algorithm:

Consider a circular track where hare and tortoise are racing. It takes ‘n’ steps to complete the track. But Hare is twice as fast as the tortoise.So if both start from start they will meet again at the start of the lap.

Now let us consider a race where the hare starts k steps ahead of tortoise. Now hare has a head start and also is twice as fast. If they run now they will meet K steps behind the start of the lap.

So now applying this to our list. Both hare and tortoise start at first node but hare is twice as fast. When the tortoise enters the loop at 40, the hare has already entered the loop and is K nodes ahead of tortoise. K nodes is the no of nodes from the first node to the start of the loop. now applying the track theory here both of them meet k nodes before the start of the loop.

For example : when tortoise comes to 40 hare is at 20 inside the loop.then they both meet at 20.

Now send tortoise back to first node in the list. Let them both iterate at same speed(one node per step) then

tortoise : 60->50->40 (traverses 2 nodes)
hare : 20->10->40 (traverses 2 nodes from meeting point to start of loop)

so moving k nodes from start of list and from meeting point of hare and tortoise gives the start of the loop.

class Node
{
	public int item;
	public Node next;
	public Node(int val)
	{
		item = val;
	}
	public void displayNode()
	{
		System.out.println("[" + item + "] ");
	}
} 
class LinkedList
{
	private Node first;
	public LinkedList()
	{
		first = null;
	}
	public boolean isEmpty()
	{
		return (first==null);
	}
	public void insert(int val)//inserts at beginning of list
	{
		Node newNode = new Node(val);
		newNode.next = first;
		first = newNode;
	}
	public Node delete()//deletes at beginning of list
	{
		Node temp = first;
		first = first.next;
		return temp;
	}
	public void display()
	{
		System.out.println("List items from first to last :");
		Node current = first;
		while(current != null)
		{
			current.displayNode();
			current = current.next; 
		}
		System.out.println("");
	}
	public void reverse() 
	{
		Node current = first;
    		first = null;
    		while (current != null) 
		{
		        Node save = current;
		        current = current.next;
		        save.next = first;
		        first = save;
		}
	}
	public Node search(int val)
	{
		Node current = first;
		while(current.item != val)
		{
			if(current.next == null)
				return null;
			else
				current = current.next;
		}
		return current;
	}
	public Node delete(int val)
	{
		Node current = first;
		Node previous = first;
		while(current.item != val)
		{
			if(current.next == null)
				return null;
			else
			{
				previous = current;
				current = current.next;
			}
		}
		if(current == first)
			first = first.next;
		else
			previous.next = current.next;
		return current;
	}
	public Node FindLoop()
	{
		Node tortoise = first;
		Node hare = first;
		
		while (hare.next != null)
		{
			tortoise = tortoise.next;
			hare = hare.next.next;
			if( tortoise == hare)
			{
				break;
			}
		}
		
		if( hare.next == null)
		{
			return null;
		}
		
		tortoise = first;
		while (tortoise != hare)
		{
			tortoise = tortoise.next;
			hare = hare.next;
		}
		return hare;
	}
	
} 
class LinkedListBlog
{
	public static void main(String[] args)
	{
		LinkedList object = new LinkedList();
		object.insert(10);
		object.insert(20);
		object.insert(30);
		object.insert(40);
		object.insert(50);
		object.insert(60);

		object.display();

		Node tempObj1 = object.search(40);//creating a loop 60->50->40->30->20->10->40
		Node tempObj2 = object.search(10);
		
		tempObj2.next = tempObj1;
		Node loop = object.FindLoop();
		if(loop != null)
			System.out.println("Loop exists and starts at : " + loop.item);
		else
			System.out.println("there is no loop");
		object.display();
		
	} 
}

OUTPUT:Redirecting to a file. If a loop exits then display() is in an infinte loop

List items from first to last :
[60]
[50]
[40]
[30]
[20]
[10]

Loop exists and starts at : 40
List items from first to last :
[60]
[50]
[40]
[30]
[20]
[10]
[40]
[30]
[20]
[10]
[40]
[30]
[20]
[10]
[40]
[30]
[20]
[10]
[40]
[30]
[20]
[10]
[40]
[30]

its in a infinite loop if we try to display the list and yeah off course you cannot reverse this corrupt list

2 responses to “Floyd Cycle Detection Algorithm or “Tortoise and Hare Algorithm” for finding a loop in a Linked List.

  1. Reader April 14, 2012 at 1:30 pm

    nice explanation, thanks

  2. SM October 28, 2012 at 2:33 am

    Dear Chinmaya, (Saw your blog entry on Hare and Tortoise)… Could you please tell me whether the speeds of 2x and 5x or 21x and 55x (co-primes) are OK for detecting cycles rather than the traditional x and 2x? What difference does it make. Also I can’t seem to understand why the T and H should meet at the node k nodes before entry point whenever the length of the list excluding (before) the loop is k? Does this only work when the speeds are x and 2x or all the time?
    Please throw some light on it for me… Thanks.

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

%d bloggers like this: