Geek Answers Handbook

Define a loop or recursion in a list

I want to identify a loop or recursion in a list for below node structure. 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 points to Node4 , and here comes a loop or recursion, and my code will be infinite. So, what if I want to know this type of scenario with the optimal level of performance?

+6
source share
7 answers

This is an interview question that I heard several times. Although I never tried to implement any kind of loop detection, the answer that most interviewers seem to like is to repeat the list and store the visited nodes in a hash table. If you encounter a conflict while storing in a table, you have a loop in your list.

Edit: in an attempt to suggest some code for an example, this is what I will probably try to do (assuming you have some kind of LinkedList<EntityNode> object). I updated this to use a HashSet instead of a HashMap, so it was simpler (as PM 77-1 pointed out).

 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 have not had the opportunity to verify this, but it should work. The reason is that the add() method for HashSet returns true if this set did not already contain the specified element . Therefore, if an EntityNode already exists in the set, it will return false, which means that a loop has been detected.

Since my answer has already been removed, I want to say that there are other solutions. Another that was noted in this thread is the turtle and the hare algorithm. You can find more information about this in this thread or on this wiki page .

+15
source

You must have two EntityNode objects. Both run in Node1. The first object move two nodes down, and the second - only one node down. Repeat this until you reach the end (there was no loop), or two objects meet at the same node (there is a loop).

In your example:

n1: Node1, n2: Node1

n1: Node3, n2: Node2

n1: Node5, n2: Node3

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

For pseudocode:

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

I searched 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 links to the list and move them at different speeds . Move one forward to 1 node and the other to nodes 2 .

  • If the linked list has a loop, it will definitely meet.
  • Another of the two links (or their next ) will become null .

Java code that implements 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; } }
+3
source

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

+2
source

I like the answer of Bhavik if you are limited by memory restrictions. It does not create any possible objects to determine the answer.

If there is a loop, then the one-step and two-step methods of passing through EntityNodes must 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; }
0
source

Just move the list, keeping every node visited in a hash set. If the node you are adding is already in the set, you have a loop.

0
source

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

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

C. The index of the nodes when they are created. If node.nextNode.Index-1! = Node.Index, you have recursion.

0
source

More articles:


All Articles