import java.util.HashSet;
import java.util.Set;
public class FirstOverlapDetection {
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("firstOverlapBrutalForce: " + firstOverlapBrutalForce(head1, head2).value);
head1 = createLinkedList1();
head2 = createLinkedList2();
System.out.println("firstOverlapSlowFastPointer: " + firstOverlapSlowFastPointer(head1, head2).value);
head1 = createLinkedList1();
head2 = createLinkedList2();
System.out.println("firstOverlapCommonTail: " + firstOverlapCommonTail(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> 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 current;
current = current.next;
}
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 firstOverlapCommonTail(LNode head1, LNode head2) {
if(head1 == null || head1.next == null ||
head2 == null || head2.next == null) return null;
LNode current = head1.next;
int count1 = 0;
while(current.next != null) {
current = current.next;
count1 ++;
}
LNode tail1 = current;
current = head2.next;
int count2 = 0;
while(current.next != null) {
current = current.next;
count2 ++;
}
if(tail1 != current)
return null;
int delta = 0;
LNode start = head1.next;
LNode start2 = head2.next;
if(count1 > count2) {
delta = count1 - count2;
for(int i = 0; i < delta; i++) {
start = start.next;
}
while(start != start2) {
start = start.next;
start2 = start2.next;
}
return start;
} else {
delta = count2 - count1;
for(int i = 0; i < delta; i++) {
start2 = start2.next;
}
while(start != start2) {
start = start.next;
start2 = start2.next;
}
return start;
}
}
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;
}
}
}
