import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import org.junit.Test;
public class OverlapDetectionTest {
private LNode createLinkedList1(int numOfNode) {
LNode head = new LNode(0, null);
LNode current = new LNode(1, null);
head.next = current;
for(int i = 2; i <= numOfNode; i++) {
current.next = new LNode(i, null);
current = current.next;
}
return head;
}
public static LNode createLinkedList2(int numOfNode, LNode common) {
LNode head = new LNode(0, null);
LNode current = new LNode(10, null);
head.next = current;
for(int i = 2; i <= numOfNode; i++) {
current.next = new LNode(i*10, null);
current = current.next;
}
current.next = common;
return head;
}
private LNode getHeadNode(LNode head, int headNodePos) {
LNode current = head.next;
for(int i = 1; i < headNodePos; i++) {
current = current.next;
}
return current;
}
@Test
public void testNoOverlap() {
System.out.println("testNoOverlap");
LNode head1 = createLinkedList1(2);
LNode head2 = createLinkedList1(5);
OverlapDetection.printResult(head1);
OverlapDetection.printResult(head2);
assertFalse(OverlapDetection.hasOverlapBrutalForce(head1, head2));
head1 = createLinkedList1(1);
head2 = createLinkedList1(1);
OverlapDetection.printResult(head1);
OverlapDetection.printResult(head2);
assertFalse(OverlapDetection.hasOverlapSlowFastPointer(head1, head2));
head1 = createLinkedList1(10);
head2 = createLinkedList1(9);
OverlapDetection.printResult(head1);
OverlapDetection.printResult(head2);
assertFalse(OverlapDetection.hasOverlapCommonTail(head1, head2));
}
@Test
public void testOverlap() {
System.out.println("testOverlap");
int numOfNode = 5;
int headNodePos = 2;
int L = 3;
LNode head1 = createLinkedList1(numOfNode);
LNode head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));
OverlapDetection.printResult(head1);
OverlapDetection.printResult(head2);
assertTrue(OverlapDetection.hasOverlapBrutalForce(head1, head2));
head1 = createLinkedList1(numOfNode);
head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));
assertTrue(OverlapDetection.hasOverlapSlowFastPointer(head1, head2));
head1 = createLinkedList1(numOfNode);
head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));
assertTrue(OverlapDetection.hasOverlapCommonTail(head1, head2));
numOfNode = 9;
headNodePos = 3;
L = 1;
head1 = createLinkedList1(numOfNode);
head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));
OverlapDetection.printResult(head1);
OverlapDetection.printResult(head2);
assertTrue(OverlapDetection.hasOverlapBrutalForce(head1, head2));
head1 = createLinkedList1(numOfNode);
head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));
assertTrue(OverlapDetection.hasOverlapSlowFastPointer(head1, head2));
head1 = createLinkedList1(numOfNode);
head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));
assertTrue(OverlapDetection.hasOverlapCommonTail(head1, head2));
numOfNode = 2;
headNodePos = 2;
L = 5;
head1 = createLinkedList1(numOfNode);
head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));
OverlapDetection.printResult(head1);
OverlapDetection.printResult(head2);
assertTrue(OverlapDetection.hasOverlapBrutalForce(head1, head2));
head1 = createLinkedList1(numOfNode);
head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));
assertTrue(OverlapDetection.hasOverlapSlowFastPointer(head1, head2));
head1 = createLinkedList1(numOfNode);
head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));
assertTrue(OverlapDetection.hasOverlapCommonTail(head1, head2));
numOfNode = 1;
headNodePos = 1;
L = 5;
head1 = createLinkedList1(numOfNode);
head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));
OverlapDetection.printResult(head1);
OverlapDetection.printResult(head2);
assertTrue(OverlapDetection.hasOverlapBrutalForce(head1, head2));
head1 = createLinkedList1(numOfNode);
head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));
assertTrue(OverlapDetection.hasOverlapSlowFastPointer(head1, head2));
head1 = createLinkedList1(numOfNode);
head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));
assertTrue(OverlapDetection.hasOverlapCommonTail(head1, head2));
numOfNode = 15;
head1 = createLinkedList1(numOfNode);
OverlapDetection.printResult(head1);
OverlapDetection.printResult(head1);
assertTrue(OverlapDetection.hasOverlapBrutalForce(head1, head1));
head1 = createLinkedList1(numOfNode);
assertTrue(OverlapDetection.hasOverlapSlowFastPointer(head1, head1));
head1 = createLinkedList1(numOfNode);
assertTrue(OverlapDetection.hasOverlapCommonTail(head1, head1));
}
@Test
public void testNull() {
LNode head1 = null;
LNode head2 = null;
assertFalse(OverlapDetection.hasOverlapBrutalForce(head1, head2));
head1 = null;
head2 = null;
assertFalse(OverlapDetection.hasOverlapSlowFastPointer(head1, head2));
head1 = null;
head2 = null;
assertFalse(OverlapDetection.hasOverlapCommonTail(head1, head2));
head1 = new LNode(0, null);
head2 = null;
assertFalse(OverlapDetection.hasOverlapBrutalForce(head1, head2));
head1 = new LNode(0, null);
head2 = null;
assertFalse(OverlapDetection.hasOverlapSlowFastPointer(head1, head2));
head1 = new LNode(0, null);
head2 = null;
assertFalse(OverlapDetection.hasOverlapCommonTail(head1, head2));
head2 = new LNode(0, null);
head1 = null;
assertFalse(OverlapDetection.hasOverlapBrutalForce(head1, head2));
head2 = new LNode(0, null);
head1 = null;
assertFalse(OverlapDetection.hasOverlapSlowFastPointer(head1, head2));
head2 = new LNode(0, null);
head1 = null;
assertFalse(OverlapDetection.hasOverlapCommonTail(head1, head2));
}
}
