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;
  }
}

Answer 4

I think you can make a "visited" flag. Or you can use unintersecting sets, which helps to identify loops in O(N *log N).
P.S. I must admit that this method is more appropriate if you need to build a graph without cycles.

Answer 5

I like Bhavik's answer if you are constrained by memory limits. It doesn't create any possibly large objects to determine the answer.

If there is a loop then the single step and double step methods of walking through the EntityNodes will have to intersect.

Here is sample code to test with -

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

    public static void main(String[] args) {
        final EntityNode head = new EntityNode();

        // Create small sample (test with even and odd number)
        EntityNode tail = head;
        for (int i = 0; i < 6; i++) {
            EntityNode newNode = new EntityNode();
            tail.nextNode = newNode;
            tail = newNode;
        }

        // Add "loop" node
        tail.nextNode = head;

        System.out.println(detectLoop(head));
    }

    // Return true if a loop is found
    private static boolean detectLoop(EntityNode head) {
        boolean loopDetected = false;

        if (head != null) {
            EntityNode singleStep = head;
            EntityNode doubleStep = head;

            // If either EntityNode is null and end has been found
            while ((singleStep.nextNode != null)
                    && (doubleStep.nextNode != null)) {
                singleStep = singleStep.nextNode;

                // Assert doubleStepper.nextNode != null
                doubleStep = doubleStep.nextNode.nextNode;

                // If there is a "Collision" then there is a loop
                loopDetected = (doubleStep == singleStep);
                if (loopDetected) {
                    break;
                }
            }
        }
        return loopDetected;
    }

Answer 6

Just traverse the list while keeping every visited node in a hash set. If the node you are adding is ever already present in the set, you have a cycle.

Answer 7

A.-Keep count of the amount of added nodes. Then start a loop through them, while counting the loops. If loopsAmount>nodesAmount, you have recursion.

B.-Keep track of the visited nodes. If a node is visited twice, you have recursion.

C.-Index the nodes while creating them. If node.nextNode.Index-1 != node.Index, you have recursion.