import java.util.HashSet;
import java.util.Set;
/**
*
* Given a linked list, detect if the linked list has a loop. If there is a node whose next pointer point
* to a node before it, a loop is detected.
*
*
*/
public class LoopDetectionSolutionOne {
static LNode loopHead;
public static void main(String...args) {
LNode head = createLinkedList();
printResult(head, loopHead);
System.out.println();
System.out.println("hasLoopBrutalForce: " + hasLoopBrutalForce(head));
System.out.println("hasLoopSlowFastPointer: " + hasLoopSlowFastPointer(head));
}
public static boolean hasLoopBrutalForce(LNode head) {
if(head == null || head.next == null) return false;
Set<LNode> visited = new HashSet<>();
LNode current = head.next;
while(current != null) {
if(visited.contains(current)) return true;
visited.add(current);
current = current.next;
}
return false;
}
public static boolean hasLoopSlowFastPointer(LNode head) {
if(head == null || head.next == null) return false;
LNode slowPointer = head.next;
LNode fastPointer = head.next;
while(fastPointer != null && fastPointer.next != null) {
slowPointer = slowPointer.next;
fastPointer = fastPointer.next.next;
if(slowPointer == fastPointer) return true;
}
return false;
}
public static LNode createLinkedList() {
LNode head = new LNode(0, null);
LNode current = new LNode(1, null);
head.next = current;
current.next = new LNode(2, null);
current = current.next;
current.next = new LNode(3, null);
current = current.next;
current.next = new LNode(4, null);
current = current.next;
loopHead = current;
current.next = new LNode(5, null);
current = current.next;
current.next = new LNode(6, null);
current = current.next;
current.next = new LNode(7, null);
current = current.next;
current.next = loopHead;
return head;
}
public static void printResult(LNode head, LNode loopHead) {
System.out.println();
if(head == null || head.next == null) return;
LNode current = head.next;
int count = 0;
while(current.next != null && count <= 1) {
if(current == loopHead) count ++;
System.out.print(current.value + " ");
current = current.next;
}
}
}
