import java.util.HashSet;
import java.util.Set;
public class OverlapDetection {
static LNode loopHead;
public static void main(String...args) {
LNode head1 = createLinkedList1();
LNode head2 = createLinkedList2();
printResult(head1);
System.out.println();
printResult(head2);
System.out.println();
System.out.println("hasOverlapBrutalForce: " + hasOverlapBrutalForce(head1, head2));
head1 = createLinkedList1();
head2 = createLinkedList2();
System.out.println("hasOverlapSlowFastPointer: " + hasOverlapSlowFastPointer(head1, head2));
head1 = createLinkedList1();
head2 = createLinkedList2();
System.out.println("hasOverlapCommonTail: " + hasOverlapSlowFastPointer(head1, head2));
}
public static boolean hasOverlapBrutalForce(LNode head1, LNode head2) {
if(head1 == null || head1.next == null ||
head2 == null || head2.next == null) return false;
Set<LNode> visited = new HashSet<>();
LNode current = head1.next;
while(current != null) {
visited.add(current);
current = current.next;
}
current = head2.next;
while(current != null) {
if(visited.contains(current))
return true;
current = current.next;
}
return false;
}
public static boolean hasOverlapSlowFastPointer(LNode head1, LNode head2) {
if(head1 == null || head1.next == null ||
head2 == null || head2.next == null) return false;
LNode current = head1.next;
while(current.next != null) {
current = current.next;
}
//link the first linked list's tail to the head of the second linked list.
current.next = head2;
LNode slowPointer = head2.next;
LNode fastPointer = head2.next;
while(fastPointer != null && fastPointer.next != null) {
slowPointer = slowPointer.next;
fastPointer = fastPointer.next.next;
if(slowPointer == fastPointer) return true;
}
return false;
}
public static boolean hasOverlapCommonTail(LNode head1, LNode head2) {
if(head1 == null || head1.next == null ||
head2 == null || head2.next == null) return false;
LNode current = head1.next;
while(current.next != null) {
current = current.next;
}
LNode tail1 = current;
current = head2.next;
while(current.next != null) {
current = current.next;
}
return tail1 == current;
}
public static LNode createLinkedList1() {
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);
return head;
}
public static LNode createLinkedList2() {
LNode head = new LNode(0, null);
LNode current = new LNode(11, null);
head.next = current;
current.next = new LNode(22, null);
current = current.next;
current.next = new LNode(33, null);
current = current.next;
current.next = loopHead;
return head;
}
public static void printResult(LNode head) {
System.out.println();
if(head == null || head.next == null) return;
LNode current = head.next;
while(current != null) {
System.out.print(current.value + " ");
current = current.next;
}
}
}
