Identify loop or recursion in the list

Question

I want to identify the loop or recursion in the list for the below structure of the node. How can I identify the same?

public class EntityNode {
    private EntityNode nextNode; // Points to the next node
}

Example,

Node1 -> Node2 -> Node3 -> Node4 -> Node5 -> Node6 -> Node4

Here, you can see that Node6 is pointing to Node4, and here there comes the looping or recursion and my code will go into infinite. So what if I want to find out this type of scenario with the optimum performance level?

Answer 1

This is actually an interview question I have heard a few times. While I have never tried to implement any sort of loop detection, the answer that most of the interviewers seemed to like is iterating through the list and storing the visited nodes in a hashtable. If you get a collision while storing into the table, then you have a loop in your list.

Edit: In an attempt to offer some code for the example, here is what I would probably try to do (assuming you have some sort of LinkedList<EntityNode> object). I updated this to use a HashSet instead of a HashMap so it was more straightforward (as pointed out by PM 77-1).

public bool detectLoop(LinkedList<EntityNode> list)
{
    Set<EntityNode> nodeSet = new HashSet<EntityNode>();
    EntityNode curNode = list.getHead();
    boolean loopDetected = false;

    if(curNode != null)
    {
        while(curNode.getNextNode() != null && !loopDetected)
        {
            cureNode = curNode.getNextNode();
            loopDetected = !nodeSet.add(curNode);
        }
    }

    return loopDetected;
}

I haven't had the opportunity to test this, but this should work. The reason being that the add() method for a HashSet returns true if this set did not already contain the specified element. So if there is a EntityNode already exists in the set, it will return false, meaning that there was a loop detected.

Since my answer has sort of taken off, I want to say that there are other solutions to this as well. The other one that has been pointed out in this thread is the tortoise and the hare algorithm. You can find more information on that in this thread or at this wiki page.

Answer 2

You should have two EntityNode objects. Both start at Node1. Have the first object move two nodes down, and the second only move one node down. Repeat this until you either reach the end (there was no cycle) or the two objects meet at the same node (there is a cycle).

For your example:

n1: Node1, n2: Node1

n1: Node3, n2: Node2

n1: Node5, n2: Node3

n1: Node4, n2: Node4 -> cycle!!

---

For pseudocode:

while (n1.nextNode isn't null):
    n1 = n1.nextNode.nextNode
    n2 = n2.nextnode
    if (n1 equals n2): return 'there is a loop!'

Answer 3

I searched on the net and found that this type of problem is called the tortoise and hare algorithm. The Wikipedia page is also here for the same.

As codaddict states in their answer here:

The idea is to have two references to the list and move them at different speeds. Move one forward by 1 node and the other by 2 nodes.

• If the linked list has a loop they will definitely meet.
• Else either of the two references(or their next) will become null.

Java code implementing the algorithm:

boolean hasLoop(EntityNode first) {
  if (first == null) // list does not exist..so no loop either.
      return false;
  EntityNode slow, fast; // create two references.
  slow = fast = first; // make both refer to the start of the list.
  while (true) {
      slow = slow.nextNode; // 1 hop.
      if (fast.nextNode != null)
          fast = fast.nextNode; // 2 hops.
      else
          return false; // next node null => no loop.
      if (slow == null || fast == null) // if either hits null..no loop.
          return false;
      if (slow == fast) // if the two ever meet...we must have a loop.
          return true;
  }
}