How to detect a loop in a linked list

Question

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

User · Answer

Here is my solution in java  boolean detectLoop Node head       Node fastRunner   head      Node slowRunner   head      while fastRunner    null  amp  amp  slowRunner   null  amp  amp  fastRunner next    null           fastRunner   fastRunner next next          slowRunner   slowRunner next          if fastRunner    slowRunner               return true                      return false

User · Answer

This approach has space overhead  but a simpler implementation   Loop can be identified by storing nodes in a Map  And before putting the node  check if node already exists  If node already exists in the map then it means that Linked List has loop   public boolean loopDetector Node lt E gt  first             Node lt E gt  t   first           Map lt Node lt E gt   Node lt E gt  gt  map   new IdentityHashMap lt Node lt E gt   Node lt E gt  gt              while  t    null                  if  map containsKey t                        System out println   duplicate Node is --    t                                  having value      t data                       return true                  else                      map put t  t                                 t   t next                      return false

User · Answer

To detect whether a circular loop exists in a linked list public boolean findCircularLoop         Node slower  faster      slower   head      faster   head next     start faster one node ahead     while  true                if the faster pointer encounters a NULL element         if  faster    null    faster next    null              return false             if faster pointer ever equals slower or faster s next            pointer is ever equal to slower then it s a circular list         else if  slower    faster    slower    faster next              return true          else                  advance the pointers             slower   slower next              faster   faster next next

User · Answer

I cannot see any way of making this take a fixed amount of time or space  both will increase with the size of the list   I would make use of an IdentityHashMap  given that there is not yet an IdentityHashSet  and store each Node into the map   Before a node is stored you would call containsKey on it   If the Node already exists you have a cycle   ItentityHashMap uses    instead of  equals so that you are checking where the object is in memory rather than if it has the same contents

User · Answer

An alternative solution to the Turtle and Rabbit  not quite as nice  as I temporarily change the list   The idea is to walk the list  and reverse it as you go  Then  when you first reach a node that has already been visited  its next pointer will point  backwards   causing the iteration to proceed towards first again  where it terminates   Node prev   null  Node cur   first  while  cur    null        Node next   cur next      cur next   prev      prev   cur      cur   next    boolean hasCycle   prev    first  amp  amp  first    null  amp  amp  first next    null      reconstruct the list cur   prev  prev   null  while  cur    null        Node next   cur next      cur next   prev      prev   cur      cur   next     return hasCycle    Test code   static void assertSameOrder Node   nodes        for  int i   0  i  lt  nodes length - 1  i              assert nodes i  next    nodes i   1            public static void main String   args        Node   nodes   new Node 100       for  int i   0  i  lt  nodes length  i              nodes i    new Node              for  int i   0  i  lt  nodes length - 1  i              nodes i  next   nodes i   1             Node first   nodes 0       Node max   nodes nodes length - 1        max next   null      assert  hasCycle first       assertSameOrder nodes       max next   first      assert hasCycle first       assertSameOrder nodes       max next   max      assert hasCycle first       assertSameOrder nodes       max next   nodes 50       assert hasCycle first       assertSameOrder nodes

User · Answer

public boolean hasLoop Node start         TreeSet lt Node gt  set   new TreeSet lt Node gt        Node lookingAt   start      while  lookingAt peek      null          lookingAt   lookingAt next          if  set contains lookingAt              return false            else           set put lookingAt                      return true          Inside our Node class          public Node peek       return this next      Forgive me my ignorance  I m still fairly new to Java and programming   but why wouldn t the above work    I guess this doesn t solve the constant space issue    but it does at least get there in a reasonable time  correct  It will only take the space of the linked list plus the space of a set with n elements  where n is the number of elements in the linked list  or the number of elements until it reaches a loop   And for time  worst-case analysis  I think  would suggest O nlog n    SortedSet look-ups for contains   are log n   check the javadoc  but I m pretty sure TreeSet s underlying structure is TreeMap  whose in turn is a red-black tree   and in the worst case  no loops  or loop at very end   it will have to do n look-ups

User · Answer

Tortoise and hare  Take a look at Pollard s rho algorithm   It s not quite the same problem  but maybe you ll understand the logic from it  and apply it for linked lists    if you re lazy  you can just check out cycle detection -- check the part about the tortoise and hare    This only requires linear time  and 2 extra pointers   In Java   boolean hasLoop  Node first         if   first    null   return false       Node turtle   first      Node hare   first       while   hare next    null  amp  amp  hare next next    null              turtle   turtle next           hare   hare next next            if   turtle    hare   return true             return false       Most of the solution do not check for both next and next next for nulls   Also  since the turtle is always behind  you don t have to check it for null -- the hare did that already

User · Answer

Here is the solution for detecting the cycle   public boolean hasCycle ListNode head                ListNode slow  head              ListNode fast  head               while fast  null  amp  amp  fast next  null                   slow   slow next     slow pointer only one hop                 fast   fast next next     fast pointer two hops                   if slow    fast     return true     retrun true if fast meet slow pointer                            return false     return false if fast pointer stop at end

User · Answer

You may use Floyd s tortoise algorithm as suggested in above answers as well   This algorithm can check if a singly linked list has a closed cycle  This can be achieved by iterating a list with two pointers that will move in different speed  In this way  if there is a cycle the two pointers will meet at some point in the future   Please feel free to check out my blog post on the linked lists data structure  where I also included a code snippet with an implementation of the above-mentioned algorithm in java language   Regards   Andreas   xnorcode

User · Answer

The user unicornaddict has a nice algorithm above  but unfortunately it contains a bug for non-loopy lists of odd length    3  The problem is that fast can get  stuck  just before the end of the list  slow catches up to it  and a loop is  wrongly  detected   Here s the corrected algorithm   static 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   null          else             fast   fast next next     2 hops           if fast    null     if fast hits null  no loop              return false           if slow    fast     if the two ever meet   we must have a loop              return true

User · Answer

public boolean isCircular          if  head    null          return false       Node temp1   head      Node temp2   head       try           while  temp2 next    null                 temp2   temp2 next next next              temp1   temp1 next               if  temp1    temp2    temp1    temp2 next                   return true                       catch  NullPointerException ex            return false              return false

User · Answer

You could even do it in constant O 1  time  although it would not be very fast or efficient   There is a limited amount of nodes your computer s memory can hold  say N records  If you traverse more than N records  then you have a loop

User · Answer

Algorithm  public static boolean hasCycle  LinkedList lt Node gt  list        HashSet lt Node gt  visited   new HashSet lt Node gt          for  Node n   list                visited add n            if  visited contains n next                         return true                       return false      Complexity  Time   O n  Space   O n

User · Answer

In this context  there are loads to textual materials everywhere  I just wanted to post a diagrammatic representation that really helped me to grasp the concept   When fast and slow meet at point p    Distance travelled by fast   a b c b   a 2b c   Distance travelled by slow   a b  Since the fast is 2 times faster than the slow   So a 2b c   2 a b   then we get a c   So when another slow pointer runs again from head to q  at the same time  fast pointer will run from p to q  so they meet at the point q together     public ListNode detectCycle ListNode head        if head    null    head next  null          return null       ListNode slow   head      ListNode fast   head       while  fast  null  amp  amp  fast next  null           fast   fast next next          slow   slow next                      if the 2 pointers meet  then the          dist from the meeting pt to start of loop          equals         dist from head to start of loop                    if  fast    slow     loop found             slow   head              while slow    fast                   slow   slow next                  fast   fast next                            return slow                                  return null

User · Answer

If we re allowed to embed the class Node  I would solve the problem as I ve implemented it below  hasLoop   runs in O n  time  and takes only the space of counter  Does this seem like an appropriate solution  Or is there a way to do it without embedding Node   Obviously  in a real implementation there would be more methods  like RemoveNode Node n   etc    public class LinkedNodeList       Node first      Int count       LinkedNodeList            first   null          count   0             LinkedNodeList Node n           if  n next    null               throw new error  must start with single node               else               first   n              count   1                       public void addNode Node n           Node lookingAt   first           while lookingAt next    null               lookingAt   lookingAt next                     lookingAt next   n          count               public boolean hasLoop             int counter   0          Node lookingAt   first           while lookingAt next    null               counter                if  count  lt  counter                   return false                else                  lookingAt   lookingAt next                                   return true                private class Node          Node next

User · Answer

This code is optimized and will produce result faster than with the one chosen as the best answer This code saves from going into a very long process of chasing the forward and backward node pointer which will occur in the following case if we follow the  best answer  method Look through the dry run of the following and you will realize what I am trying to say Then look at the problem through the given method below and measure the no  of steps taken to find the answer   1- 2- 9- 3  --------    Here is the code   boolean loop node  head     node  back head   node  front head    while front  amp  amp  front- gt next       front front- gt next- gt next    if back  front    return true    else   back back- gt next     return false

User · Answer

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   gt  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

User · Answer

linked list find loop function  int findLoop struct Node  head        struct Node  slow   head   fast   head      while slow  amp  amp  fast  amp  amp  fast- gt next                slow   slow- gt next          fast   fast- gt next- gt next          if slow    fast              return 1         return 0

User · Answer

Detecting a loop in a linked list can be done in one of the simplest ways  which results in O N  complexity using hashmap or O NlogN  using a sort based approach   As you traverse the list starting from head  create a sorted list of addresses  When you insert a new address  check if the address is already there in the sorted list  which takes O logN  complexity

User · Answer

The following may not be the best method--it is O n 2    However  it should serve to get the job done  eventually    count of elements so far   0  for  each element in linked list        search for current element in first  lt count of elements so far gt      if found  then you have a loop     else count of elements so far

User · Answer

boolean hasCycle Node head         boolean dec   false      Node first   head      Node sec   head      while first    null  amp  amp  sec    null                first   first next          sec   sec next next          if first    sec                         dec   true              break                           return dec      Use above function to detect a loop in linkedlist in java

User · Answer

Here is my runnable code    What I have done is to reveres the linked list by using three temporary nodes  space complexity O 1   that keep track of the links    The interesting fact about doing it is to help detect the cycle in the linked list because as you go forward  you don t expect to go back to the starting point  root node  and one of the temporary nodes should go to null unless you have a cycle which means it points to the root node    The time complexity of this algorithm is O n  and space complexity is O 1    Here is the class node for the linked list   public class LinkedNode      public LinkedNode next      Here is the main code with a simple test case of three nodes that the last node pointing to the second node       public static boolean checkLoopInLinkedList LinkedNode root            if  root    null    root next    null  return false           LinkedNode current1   root  current2   root next  current3   root next next          root next   null          current2 next   current1           while current3    null               if current3    root  return true               current1   current2              current2   current3              current3   current3 next               current2 next   current1                    return false          Here is the a simple test case of three nodes that the last node pointing to the second node   public class questions      public static void main String    args            LinkedNode n1   new LinkedNode            LinkedNode n2   new LinkedNode            LinkedNode n3   new LinkedNode            n1 next   n2          n2 next   n3          n3 next   n2           System out print checkLoopInLinkedList n1

User · Answer

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  amp  amp  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

User · Answer

I might be terribly late and new to handle this thread  But still    Why cant the address of the node and the  next  node pointed be stored in a table  If we could tabulate this way  node present   present node addr   next node address   node 1  addr1  0x100 addr2  0x200   no present node address till this point had 0x200  node 2  addr2  0x200 addr3  0x300   no present node address till this point had 0x300  node 3  addr3  0x300 addr4  0x400   no present node address till this point had 0x400  node 4  addr4  0x400 addr5  0x500   no present node address till this point had 0x500  node 5  addr5  0x500 addr6  0x600   no present node address till this point had 0x600  node 6  addr6  0x600 addr4  0x400   ONE present node address till this point had 0x400    Hence there is a cycle formed

User · Answer

Better than Floyd s algorithm  Richard Brent described an alternative cycle detection algorithm  which is pretty much like the hare and the tortoise  Floyd s cycle  except that  the slow node here doesn t move  but is later  teleported  to the position of the fast node at fixed intervals    The description is available here   http   www siafoo net algorithm 11 Brent claims that his algorithm is 24 to 36   faster than the Floyd s cycle algorithm   O n  time complexity  O 1  space complexity   public static boolean hasLoop Node root       if root    null  return false       Node slow   root  fast   root      int taken   0  limit   2       while  fast next    null            fast   fast next          taken            if slow    fast  return true           if taken    limit               taken   0              limit  lt  lt   1        equivalent to limit    2              slow   fast        teleporting the turtle  to the hare s position                       return false

[java] How to detect a loop in a linked list?

Examples related to java

Examples related to algorithm

Examples related to data-structures

Examples related to linked-list