How to Detect infinite loop in LinkedList with Example

This is a very common interview question. You are asked that if you have a linked list in which you can traverse only in one direction, and if that linked list has a loop in it, how you will detect it??

Well, if you don’t know the answer then don’t be demoralize. My personal opinion is that these kind of questions does not evaluate the logical thinking of a candidate because problems like this have a very specific answer. Either you know it, or you don’t.

For this specific question, best answer interviewer is looking for is “Floyd's Cycle-Finding Algorithm“. This algorithm suggest a solution in which in stead of only one pointer to traverse through list, you are advised to have two pointers at a time. Both pointers will start from first node of linked list and traverse using next attribute.

The difference lies in the number of nodes which they jump in each step. First node jump to next node each time, where as another node jumps two nodes at a time. First node is called slower node or tortoise, and second faster node is called hare.

tortoise_and_hare_algorithm-8409248
Tortoise and hare algorithm

This traversal ensures that if there is a loop in linked link then both the nodes will meet somewhere in their traversal path for sure. It has O(n) complexity.

Lets verify this using a java example code.

I have written a least possible single linked list code for demonstration of this example only.

package com.howtodoinjava.demo.core;

public class SinglyLinkedList {

	private Node start;

	public void add(Integer i)
	{
		Node node = new Node(i);
		if(start == null)
			start = node;
		else
		{
			Node temp = start;
			while(temp.next != null)
			{
				temp = temp.next;
			}
			temp.next = node;
		}
	}

	public Node getStart()
	{
		return start;
	}

	static class Node
	{
		Node(Integer i)
		{
			this.value = i;
		}

		private Integer value;
		private Node next;
		public Integer getValue() {
			return value;
		}
		public void setValue(Integer value) {
			this.value = value;
		}
		public Node getNext() {
			return next;
		}
		public void setNext(Node next) {
			this.next = next;
		}
	}
}

Now, let test above linked list first without loop and then with loop inside it.

package com.howtodoinjava.demo.core;

public class FindLoopsInLinkedList
{
	public static void main(String args[]) {

		FindLoopsInLinkedList finder = new FindLoopsInLinkedList();

		SinglyLinkedList sampleList = new SinglyLinkedList();
		// First Insert randomly ten elements in a linked list
		for (int i = 0; i < 10; i++) {
			sampleList.add(i);
		}

		System.out.println("Loop Existence : " + finder.doesLoopExist(sampleList));
		System.out.println("Loop Existence : " + finder.doesLoopExist(finder.createLoop(sampleList)));
	}

	public boolean doesLoopExist(SinglyLinkedList listToCheck) {
		SinglyLinkedList.Node tortoise = listToCheck.getStart();
		SinglyLinkedList.Node hare = listToCheck.getStart();

		try {
			while (true) {
				tortoise = tortoise.getNext();
				hare = hare.getNext().getNext();
				if (tortoise == hare) {
					return true;
				}
			}
		} catch (NullPointerException ne) {
			return false;
		}
	}

	private SinglyLinkedList createLoop(SinglyLinkedList sampleList) {
		sampleList.getStart().getNext().getNext().getNext().setNext(sampleList.getStart().getNext());
		return sampleList;
	}
}

In above program, we have creates a linked list and the we inserted 10 elements in this list. No, when we checked the loop presence in line no. 15 it comes as false.

But, when in line 167, we have created a loop inside linked list result comes as true.

Output of above program is this:

Loop Existence : false            [Line 15]
Loop Existence : true             [Line 16]

As you see, as soon as we insert loop in line no. 16, our algorithm implementation is able to detect it.

Happy Learning !!

Was this post helpful?

Join 7000+ Awesome Developers

Get the latest updates from industry, awesome resources, blog updates and much more.

* We do not spam !!

10 thoughts on “How to Detect infinite loop in LinkedList with Example”

  1. Hi lokesh,
    I have faced this question in one my interview please solve this problem.
    thanks in advance.
    Have a  one class Person in that class id, name is there. Simulate Set using a ArrayList.
    Duplicates must not be allowed to List. Have MeSetImpl class in that class add,remove and get methods are there, in get method we pass person id and return Person object.

    Reply
  2. what was the reason behind having a static class Node, and why was it not a public class.. also can you please elaborate on inner classes and static classes

    Reply
  3. Is there any reason behind creating the SinglyLinkedList class explicitly? Can we not just use the LinkedList class from the Java library?

    Reply
  4. This was a case where in there were no duplicates . Can you please explain how can we detect a loop in case the linked list contains duplicates.

    Reply

Leave a Comment

HowToDoInJava

A blog about Java and related technologies, the best practices, algorithms, and interview questions.