Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to detect a loop in a linked list?

Say you have a linked list structure in Java. It's made up of Nodes:

class Node {     Node next;     // some user data } 

and each Node points to the next node, except for the last Node, which has null for next. Say there is a possibility that the list can contain a loop - i.e. the final Node, instead of having a null, has a reference to one of the nodes in the list which came before it.

What's the best way of writing

boolean hasLoop(Node first) 

which would return true if the given Node is the first of a list with a loop, and false otherwise? How could you write so that it takes a constant amount of space and a reasonable amount of time?

Here's a picture of what a list with a loop looks like:

alt text

like image 518
jjujuma Avatar asked Apr 18 '10 17:04

jjujuma


People also ask

How do I find a loop in a linked list?

We have used Floyd's cycle finding algorithm to check if there is a loop in LinkedList . Notice the code inside the checkLoop() method. Here, we have two variables named first and second that traverse the nodes in LinkedList . Two nodes are traversing at different speeds.

How do you find a loop node in a linked list?

Write a function findFirstLoopNode() that checks whether a given Linked List contains a loop. If the loop is present then it returns point to the first node of the loop. Else it returns NULL.

What is the best way to detect a cycle in a linked list?

A simple solution is to use hashing. The idea is to traverse the given list and insert each encountered node into a set. If the current node already presents in the set (i.e., it is seen before), that means a cycle is present in the list.

Is it possible to find a loop in a linked?

Frequently Asked Questions. How do you detect a loop in a linked list? A loop can be detected efficiently using the fast and slow pointer algorithm, where the fast pointer moves by two nodes and the slow pointer move by one node at a time.


2 Answers

You can make use of Floyd's cycle-finding algorithm, also known as tortoise and hare algorithm.

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 function implementing the algorithm:

boolean hasLoop(Node first) {      if(first == null) // list does not exist..so no loop either         return false;      Node slow, fast; // create two references.      slow = fast = first; // make both refer to the start of the list      while(true) {          slow = slow.next;          // 1 hop          if(fast.next != null)             fast = fast.next.next; // 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;     } } 
like image 103
codaddict Avatar answered Sep 25 '22 12:09

codaddict


Here's a refinement of the Fast/Slow solution, which correctly handles odd length lists and improves clarity.

boolean hasLoop(Node first) {     Node slow = first;     Node fast = first;      while(fast != null && fast.next != null) {         slow = slow.next;          // 1 hop         fast = fast.next.next;     // 2 hops           if(slow == fast)  // fast caught up to slow, so there is a loop             return true;     }     return false;  // fast reached null, so the list terminates } 
like image 23
Dave L. Avatar answered Sep 24 '22 12:09

Dave L.