import java.util.HashSet;
import java.util.Set;
public class FirstOverlapDetectionGeneral {
static LNode loopHead;
public static void main(String...args) {
LNode head1 = createLinkedList1();
LNode head2 = createLinkedList2();
printResult(head1, loopHead);
System.out.println();
printResult(head2, loopHead);
System.out.println();
System.out.println("firstOverlapBrutalForce: " + firstOverlapBrutalForce(head1, head2).value);
head1 = createLinkedList1();
head2 = createLinkedList2();
System.out.println("firstOverlapSlowFastPointer: " + firstOverlapSlowFastPointerGeneral(head1, head2).value);
}
public static LNode firstOverlapBrutalForce(LNode head1, LNode head2) {
if(head1 == null || head1.next == null ||
head2 == null || head2.next == null) return null;
Set<LNode> visited1 = new HashSet<>();
Set<LNode> visited2 = new HashSet<>();
LNode current = head1.next;
while(current != null) {
if(visited1.contains(current)) break;
visited1.add(current);
current = current.next;
}
current = head2.next;
while(current != null) {
if(visited2.contains(current)) break;
visited2.add(current);
current = current.next;
}
visited1.retainAll(visited2);
if(!visited1.isEmpty()) {
current = head1.next;
while(!visited1.contains(current))
current = current.next;
return current;
}
return null;
}
public static LNode firstOverlapSlowFastPointer(LNode head1, LNode head2) {
if(head1 == null || head1.next == null ||
head2 == null || head2.next == null) return null;
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 = head1.next;
LNode fastPointer = head1.next;
while(fastPointer != null && fastPointer.next != null) {
slowPointer = slowPointer.next;
fastPointer = fastPointer.next.next;
if(slowPointer == fastPointer) break;
}
if(fastPointer == null || fastPointer.next == null)
return null;
slowPointer = head1.next;
while(slowPointer != fastPointer) {
slowPointer = slowPointer.next;
fastPointer = fastPointer.next;
}
return fastPointer;
}
public static LNode firstOverlapSlowFastPointerGeneral(LNode head1, LNode head2) {
LNode start1 = firstOverlapNode(head1);
LNode start2 = firstOverlapNode(head2);
if((start1 == null && start2 != null) || (start1 != null && start2 == null))
return null;
if(start1 == null && start2 == null)
return firstOverlapSlowFastPointer(head1, head2); //link tail to head and detect loop solution.
else if(start1 == start2){
//convert to 2 loop-free linked lists' overlap
start1.next = null;
return firstOverlapSlowFastPointer(head1, head2);
} else {
if(!contains(head1, start1, start2)) { //no common node
return null;
}
//has 2 first common node, we return either of them
return start1;
}
}
public static boolean contains(LNode head, LNode start1, LNode start2) {
if(head == null || head.next == null) return false;
LNode current = head.next;
int count = 0;
while(current.next != null && count <= 1) {
if(current == start1) count ++;
if(current == start2) return true;
current = current.next;
}
return false;
}
public static LNode firstOverlapNode(LNode head1) {
if(head1 == null || head1.next == null) return null;
LNode slowPointer = head1.next;
LNode fastPointer = head1.next;
while(fastPointer != null && fastPointer.next != null) {
slowPointer = slowPointer.next;
fastPointer = fastPointer.next.next;
if(slowPointer == fastPointer) break;
}
if(fastPointer == null || fastPointer.next == null)
return null;
slowPointer = head1.next;
while(slowPointer != fastPointer) {
slowPointer = slowPointer.next;
fastPointer = fastPointer.next;
}
return fastPointer;
}
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);
current = current.next;
current.next = loopHead;
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, 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;
}
if(loopHead == null)
System.out.print(current.value + " ");
}
}
