/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class LoopInLinkedList {
static class Node {
public Node next;
@Override
return "Node [info=" + info + ", next=" + next.hashCode() + "]";
}
}
Node n1 = new Node();
n1.info = "A";
Node n2 = new Node();
n2.info = "B";
Node n3 = new Node();
n3.info = "C";
Node n4 = new Node();
n4.info = "D";
Node n5 = new Node();
n5.info = "E";
Node n6 = new Node();
n6.info = "F";
Node n7 = new Node();
n7.info = "G";
Node n8 = new Node();
n8.info = "H";
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n6;
n6.next = n7;
n7.next = n8;
n8.next = n2;
detectLoop(n1);
}
public static boolean detectLoop
(Node start
) throws Exception { Node slow = start;
Node fast = start;
while (slow !=null && fast != null) {
slow=slow.next;
fast=fast.next.next;
if (fast == slow) {
int k = getLengthOfLoop(fast);
Node startOfLoopNode = detectLoopStart(start, k);
System.
out.
println("Length of the loop is " + k
); System.
out.
println("Start of the loop is " + startOfLoopNode
); return true;
}
}
return false;
}
private static int getLengthOfLoop
(Node loopNode
) throws Exception { Node ptr = loopNode;
int k=0;
while ((ptr=ptr.next)!=loopNode) {
k++;
}
return k+1;
}
private static Node detectLoopStart
(Node start,
int k
) throws Exception { Node ptr1 = start;
Node ptr2 = start;
while (k-->0 && (ptr1 = ptr1.next)!=null);
while ((ptr1=ptr1.next)!=null && (ptr2=ptr2.next)!=null && ptr1 != ptr2);
return ptr1;
}
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KIGNsYXNzIExvb3BJbkxpbmtlZExpc3QgewoKICAgIHN0YXRpYyBjbGFzcyBOb2RlIHsKICAgICAgICBwdWJsaWMgU3RyaW5nIGluZm87CiAgICAgICAgcHVibGljIE5vZGUgbmV4dDsKICAgICAgICBAT3ZlcnJpZGUKICAgICAgICBwdWJsaWMgU3RyaW5nIHRvU3RyaW5nKCkgewogICAgICAgICAgICByZXR1cm4gIk5vZGUgW2luZm89IiArIGluZm8gKyAiLCBuZXh0PSIgKyBuZXh0Lmhhc2hDb2RlKCkgKyAiXSI7CiAgICAgICAgfQogICAgfQogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgdGhyb3dzIEV4Y2VwdGlvbiB7CgogICAgICAgIE5vZGUgbjEgPSBuZXcgTm9kZSgpOwogICAgICAgIG4xLmluZm8gPSAiQSI7CiAgICAgICAgTm9kZSBuMiA9IG5ldyBOb2RlKCk7CiAgICAgICAgbjIuaW5mbyA9ICJCIjsKICAgICAgICBOb2RlIG4zID0gbmV3IE5vZGUoKTsKICAgICAgICBuMy5pbmZvID0gIkMiOwogICAgICAgIE5vZGUgbjQgPSBuZXcgTm9kZSgpOwogICAgICAgIG40LmluZm8gPSAiRCI7CiAgICAgICAgTm9kZSBuNSA9IG5ldyBOb2RlKCk7CiAgICAgICAgbjUuaW5mbyA9ICJFIjsKICAgICAgICBOb2RlIG42ID0gbmV3IE5vZGUoKTsKICAgICAgICBuNi5pbmZvID0gIkYiOwogICAgICAgIE5vZGUgbjcgPSBuZXcgTm9kZSgpOwogICAgICAgIG43LmluZm8gPSAiRyI7CiAgICAgICAgTm9kZSBuOCA9IG5ldyBOb2RlKCk7CiAgICAgICAgbjguaW5mbyA9ICJIIjsKCiAgICAgICAgbjEubmV4dCA9IG4yOwogICAgICAgIG4yLm5leHQgPSBuMzsKICAgICAgICBuMy5uZXh0ID0gbjQ7CiAgICAgICAgbjQubmV4dCA9IG41OwogICAgICAgIG41Lm5leHQgPSBuNjsKICAgICAgICBuNi5uZXh0ID0gbjc7CiAgICAgICAgbjcubmV4dCA9IG44OwogICAgICAgIG44Lm5leHQgPSBuMjsKCiAgICAgICAgZGV0ZWN0TG9vcChuMSk7CiAgICB9CiAgICBwdWJsaWMgc3RhdGljIGJvb2xlYW4gZGV0ZWN0TG9vcChOb2RlIHN0YXJ0KSB0aHJvd3MgRXhjZXB0aW9uIHsKICAgICAgICBOb2RlIHNsb3cgPSBzdGFydDsKICAgICAgICBOb2RlIGZhc3QgPSBzdGFydDsKICAgICAgICB3aGlsZSAoc2xvdyAhPW51bGwgJiYgZmFzdCAhPSBudWxsKSB7CiAgICAgICAgICAgIHNsb3c9c2xvdy5uZXh0OwogICAgICAgICAgICBmYXN0PWZhc3QubmV4dC5uZXh0OwogICAgICAgICAgICBpZiAoZmFzdCA9PSBzbG93KSB7CiAgICAgICAgICAgICAgICBpbnQgayA9IGdldExlbmd0aE9mTG9vcChmYXN0KTsKICAgICAgICAgICAgICAgIE5vZGUgc3RhcnRPZkxvb3BOb2RlID0gZGV0ZWN0TG9vcFN0YXJ0KHN0YXJ0LCBrKTsKICAgICAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigiTGVuZ3RoIG9mIHRoZSBsb29wIGlzICIgKyBrKTsKICAgICAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigiU3RhcnQgb2YgdGhlIGxvb3AgaXMgIiArIHN0YXJ0T2ZMb29wTm9kZSk7CiAgICAgICAgICAgICAgICByZXR1cm4gdHJ1ZTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICByZXR1cm4gZmFsc2U7CiAgICB9CiAgICBwcml2YXRlIHN0YXRpYyBpbnQgZ2V0TGVuZ3RoT2ZMb29wKE5vZGUgbG9vcE5vZGUpIHRocm93cyBFeGNlcHRpb24gewogICAgICAgIE5vZGUgcHRyID0gbG9vcE5vZGU7CiAgICAgICAgaW50IGs9MDsKICAgICAgICB3aGlsZSAoKHB0cj1wdHIubmV4dCkhPWxvb3BOb2RlKSB7CiAgICAgICAgICAgIGsrKzsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIGsrMTsKICAgIH0KICAgIHByaXZhdGUgc3RhdGljIE5vZGUgZGV0ZWN0TG9vcFN0YXJ0KE5vZGUgc3RhcnQsIGludCBrKSB0aHJvd3MgRXhjZXB0aW9uIHsKICAgICAgICBOb2RlIHB0cjEgPSBzdGFydDsKICAgICAgICBOb2RlIHB0cjIgPSBzdGFydDsKICAgICAgICB3aGlsZSAoay0tPjAgJiYgKHB0cjEgPSBwdHIxLm5leHQpIT1udWxsKTsKICAgICAgICB3aGlsZSAoKHB0cjE9cHRyMS5uZXh0KSE9bnVsbCAmJiAocHRyMj1wdHIyLm5leHQpIT1udWxsICYmIHB0cjEgIT0gcHRyMik7CiAgICAgICAgcmV0dXJuIHB0cjE7CiAgICB9Cn0=