ISourceCode

Make the frequent cases fast and the rare case correct

Algorithm to find length of a loop in a linked list and also find length of the list

This article presents a algorithm which finds the length of a loop in a linked list and then calculate the total length of the linked list.

For basic understanding on how to detect a loop and the Floyd cycle detection (Hare and Tortoise) algorithm refer to my previous article.

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 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;
	}
	public int LoopLength(Node LoopStartNode)
	{
		Node L1 = LoopStartNode;
	       	Node L2 = LoopStartNode;
        	int loopLength = 0;
	       	do
	       	{
        		loopLength++;
	       		L2 = L2.next;
	       	}while(L1 != L2);
	       	return loopLength;
    	}
	public int ListLength(Node loopStartNode,int loopLength)
	{
	       	Node L1 = first;
	       	Node L2 = loopStartNode;
	        int length = 0;//length till the node which starts the loop
		int total;	        
		while(L1 != L2)
	        {
			L1 = L1.next;
	       		length ++;
	       	}
		total = length + loopLength;//sum of length till the node + length of loop
	       	return total;
	}
}
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);
			int loopLength = object.LoopLength(loop);
			System.out.println("Length of the loop is: " + loopLength);
			int listLength = object.ListLength(loop,loopLength);
			System.out.println("The total length of the list with a loop is: " + listLength);
		}
		else
			System.out.println("there is no loop");
		object.display();

	}
}

OUTPUT:

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

Loop exists and starts at : 40
Length of the loop is: 4
The total length of the list with a loop is: 6
List items from first to last :
[60]
[50]
[40]
[30]
[20]
[10]
[40]
[30]
[20]
[10]
[40]
[30]
[20]
[10]
[40]
[30]

the display() off course is in an infinite loop

2 responses to “Algorithm to find length of a loop in a linked list and also find length of the list

  1. sanstechbytes October 7, 2011 at 7:26 am

    Nice explanation. 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: