HowToDoInJava

  • Python
  • Java
  • Spring Boot
  • Dark Mode
Home / Java / Java Puzzles / How to Detect infinite loop in LinkedList with Example

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?

Let us know if you liked the post. That’s the only way we can improve.
TwitterFacebookLinkedInRedditPocket

About Lokesh Gupta

A family guy with fun loving nature. Love computers, programming and solving everyday problems. Find me on Facebook and Twitter.

Feedback, Discussion and Comments

  1. jana

    September 23, 2015

    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.

  2. code

    October 25, 2014

    nice!

  3. Punith

    June 10, 2014

    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

    • Lokesh Gupta

      June 10, 2014

      I will cover in future.

  4. Vivek Kumar

    April 12, 2014

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

  5. Sagar

    January 13, 2014

    Can you suggest some reference /books for learning data structures in java alongwith big-O notations

    • Lokesh Gupta

      January 13, 2014

      Not in position to recommend a book, but it will be a good start: https://www.cs.auckland.ac.nz/software/AlgAnim/ds_ToC.html

  6. Ragini

    October 4, 2013

    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.

    • Lokesh Gupta

      October 4, 2013

      How it makes a difference having duplicates in linked list? We are checking “.getNext()” references. How they will create a problem in case of duplicates??

      • Rohan

        May 22, 2017

        1->2->2->2->3->null

Comments are closed on this article!

Search Tutorials

Java Puzzles

  • Interview Puzzles List
  • Dead vs Unreachable Code
  • Palindrome Number
  • Detect infinite loop in LinkedList
  • [i += j] Vs [i = i + j]
  • HiLo Guessing Game
  • Find All Distinct Duplicate Elements
  • TreeMap Put Operation
  • String With Nth Longest Length
  • Good String Vs Bad String
  • Complete String
  • Reverse String
  • Calculate Factorial
  • FizzBuzz Solution
  • Find Missing Number From Series
  • Create Instance Without New Keyword

Java Tutorial

  • Java Introduction
  • Java Keywords
  • Java Flow Control
  • Java OOP
  • Java Inner Class
  • Java String
  • Java Enum
  • Java Collections
  • Java ArrayList
  • Java HashMap
  • Java Array
  • Java Sort
  • Java Clone
  • Java Date Time
  • Java Concurrency
  • Java Generics
  • Java Serialization
  • Java Input Output
  • Java New I/O
  • Java Exceptions
  • Java Annotations
  • Java Reflection
  • Java Garbage collection
  • Java JDBC
  • Java Security
  • Java Regex
  • Java Servlets
  • Java XML
  • Java Puzzles
  • Java Examples
  • Java Libraries
  • Java Resources
  • Java 14
  • Java 12
  • Java 11
  • Java 10
  • Java 9
  • Java 8
  • Java 7

Meta Links

  • About Me
  • Contact Us
  • Privacy policy
  • Advertise
  • Guest and Sponsored Posts

Recommended Reading

  • 10 Life Lessons
  • Secure Hash Algorithms
  • How Web Servers work?
  • How Java I/O Works Internally?
  • Best Way to Learn Java
  • Java Best Practices Guide
  • Microservices Tutorial
  • REST API Tutorial
  • How to Start New Blog

Copyright © 2020 · HowToDoInjava.com · All Rights Reserved. | Sitemap

  • Sealed Classes and Interfaces