import java.util.HashSet;
import java.util.Set;
public class LoopEntryPointSolutionOne {
static LNode loopHead;
public static void main(String...args) {
LNode head = createLinkedList();
printResult(head, loopHead);
System.out.println();
System.out.println("hasLoopBrutalForce: " + hasLoopBrutalForce(head).value);
System.out.println("hasLoopSlowFastPointer: " + hasLoopSlowFastPointer(head).value);
}
public static LNode hasLoopBrutalForce(LNode head) {
if(head == null || head.next == null) return null;
Set<LNode> visited = new HashSet<>();
LNode current = head.next;
while(current != null) {
if(visited.contains(current)) return current;
visited.add(current);
current = current.next;
}
return null;
}
public static LNode hasLoopSlowFastPointer(LNode head) {
if(head == null || head.next == null || head.next.next == null) return null;
LNode slowPointer = head.next;
LNode fastPointer = head.next;
while(fastPointer != null && fastPointer.next != null) {
slowPointer = slowPointer.next;
fastPointer = fastPointer.next.next;
if(slowPointer == fastPointer) break;
}
if(slowPointer != fastPointer) return null;
fastPointer = head.next;
while(fastPointer != slowPointer) {
fastPointer = fastPointer.next;
slowPointer = slowPointer.next;
}
return slowPointer;
}
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;
}
}
}
