fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8.  class LoopInLinkedList {
  9.  
  10.     static class Node {
  11.         public String info;
  12.         public Node next;
  13.         @Override
  14.         public String toString() {
  15.             return "Node [info=" + info + ", next=" + next.hashCode() + "]";
  16.         }
  17.     }
  18.     public static void main(String[] args) throws Exception {
  19.  
  20.         Node n1 = new Node();
  21.         n1.info = "A";
  22.         Node n2 = new Node();
  23.         n2.info = "B";
  24.         Node n3 = new Node();
  25.         n3.info = "C";
  26.         Node n4 = new Node();
  27.         n4.info = "D";
  28.         Node n5 = new Node();
  29.         n5.info = "E";
  30.         Node n6 = new Node();
  31.         n6.info = "F";
  32.         Node n7 = new Node();
  33.         n7.info = "G";
  34.         Node n8 = new Node();
  35.         n8.info = "H";
  36.  
  37.         n1.next = n2;
  38.         n2.next = n3;
  39.         n3.next = n4;
  40.         n4.next = n5;
  41.         n5.next = n6;
  42.         n6.next = n7;
  43.         n7.next = n8;
  44.         n8.next = n2;
  45.  
  46.         detectLoop(n1);
  47.     }
  48.     public static boolean detectLoop(Node start) throws Exception {
  49.         Node slow = start;
  50.         Node fast = start;
  51.         while (slow !=null && fast != null) {
  52.             slow=slow.next;
  53.             fast=fast.next.next;
  54.             if (fast == slow) {
  55.                 int k = getLengthOfLoop(fast);
  56.                 Node startOfLoopNode = detectLoopStart(start, k);
  57.                 System.out.println("Length of the loop is " + k);
  58.                 System.out.println("Start of the loop is " + startOfLoopNode);
  59.                 return true;
  60.             }
  61.         }
  62.         return false;
  63.     }
  64.     private static int getLengthOfLoop(Node loopNode) throws Exception {
  65.         Node ptr = loopNode;
  66.         int k=0;
  67.         while ((ptr=ptr.next)!=loopNode) {
  68.             k++;
  69.         }
  70.         return k+1;
  71.     }
  72.     private static Node detectLoopStart(Node start, int k) throws Exception {
  73.         Node ptr1 = start;
  74.         Node ptr2 = start;
  75.         while (k-->0 && (ptr1 = ptr1.next)!=null);
  76.         while ((ptr1=ptr1.next)!=null && (ptr2=ptr2.next)!=null && ptr1 != ptr2);
  77.         return ptr1;
  78.     }
  79. }
Success #stdin #stdout 0.1s 320576KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Length of the loop is 7
Start of the loop is Node [info=B, next=5433634]
https://ideone.com/Fb250X
Loop in a tree
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!