import static org.junit.Assert.assertTrue;
import static org.junit.Assert.assertEquals;
import org.junit.Test;
public class FirstOverlapDetectionGeneralTest {
private LNode createLinkedList1(int numOfNode, int loopPos) {
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;
}
if(loopPos > 0)
current.next = getHeadNode(head, loopPos);
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) {
if(headNodePos <= 0) return null;
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, 1);
LNode head2 = createLinkedList1(5, 1);
FirstOverlapDetectionGeneral.printResult(head1, getHeadNode(head1, 1));
FirstOverlapDetectionGeneral.printResult(head2, getHeadNode(head2, 1));
assertEquals(null, FirstOverlapDetectionGeneral.firstOverlapBrutalForce(head1, head2));
head1 = createLinkedList1(2, 1);
head2 = createLinkedList1(5, 1);
FirstOverlapDetectionGeneral.printResult(head1, getHeadNode(head1, 1));
FirstOverlapDetectionGeneral.printResult(head2, getHeadNode(head2, 1));
assertEquals(null, FirstOverlapDetectionGeneral.firstOverlapSlowFastPointerGeneral(head1, head2));
head1 = createLinkedList1(1, 1);
head2 = createLinkedList1(1, 1);
FirstOverlapDetectionGeneral.printResult(head1, getHeadNode(head1, 1));
FirstOverlapDetectionGeneral.printResult(head2, getHeadNode(head2, 1));
assertEquals(null, FirstOverlapDetectionGeneral.firstOverlapBrutalForce(head1, head2));
head1 = createLinkedList1(1, 1);
head2 = createLinkedList1(1, 1);
FirstOverlapDetectionGeneral.printResult(head1, getHeadNode(head1, 1));
FirstOverlapDetectionGeneral.printResult(head2, getHeadNode(head2, 1));
assertEquals(null, FirstOverlapDetectionGeneral.firstOverlapSlowFastPointerGeneral(head1, head2));
//loop and no loop
head1 = createLinkedList1(2, -1);
head2 = createLinkedList1(5, -1);
FirstOverlapDetectionGeneral.printResult(head1, getHeadNode(head1, -1));
FirstOverlapDetectionGeneral.printResult(head2, getHeadNode(head2, -1));
assertEquals(null, FirstOverlapDetectionGeneral.firstOverlapBrutalForce(head1, head2));
head1 = createLinkedList1(2, -1);
head2 = createLinkedList1(5, -1);
FirstOverlapDetectionGeneral.printResult(head1, getHeadNode(head1, -1));
FirstOverlapDetectionGeneral.printResult(head2, getHeadNode(head2, -1));
assertEquals(null, FirstOverlapDetectionGeneral.firstOverlapSlowFastPointerGeneral(head1, head2));
head1 = createLinkedList1(1, -1);
head2 = createLinkedList1(1, -1);
FirstOverlapDetectionGeneral.printResult(head1, getHeadNode(head1, -1));
FirstOverlapDetectionGeneral.printResult(head2, getHeadNode(head2, -1));
assertEquals(null, FirstOverlapDetectionGeneral.firstOverlapBrutalForce(head1, head2));
head1 = createLinkedList1(1, -1);
head2 = createLinkedList1(1, -1);
FirstOverlapDetectionGeneral.printResult(head1, getHeadNode(head1, -1));
FirstOverlapDetectionGeneral.printResult(head2, getHeadNode(head2, -1));
assertEquals(null, FirstOverlapDetectionGeneral.firstOverlapSlowFastPointerGeneral(head1, head2));
}
@Test
public void testOverlapLoops() {
System.out.println("testOverlapLoops");
int numOfNode = 5;
int headNodePos = 2;
int loopPos = 3;
int L = 3;
LNode head1 = createLinkedList1(numOfNode, loopPos);
LNode head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));
FirstOverlapDetectionGeneral.printResult(head1, getHeadNode(head1,loopPos));
FirstOverlapDetectionGeneral.printResult(head2, getHeadNode(head1,loopPos));
assertEquals(headNodePos, FirstOverlapDetectionGeneral.firstOverlapBrutalForce(head1, head2).value);
head1 = createLinkedList1(numOfNode, loopPos);
head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));
assertEquals(headNodePos, FirstOverlapDetectionGeneral.firstOverlapSlowFastPointerGeneral(head1, head2).value);
numOfNode = 9;
headNodePos = 5;
loopPos = 3;
L = 1;
head1 = createLinkedList1(numOfNode, loopPos);
head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));
FirstOverlapDetectionGeneral.printResult(head1, getHeadNode(head1,loopPos));
FirstOverlapDetectionGeneral.printResult(head2, getHeadNode(head1,loopPos));
assertEquals(loopPos, FirstOverlapDetectionGeneral.firstOverlapBrutalForce(head1, head2).value);
head1 = createLinkedList1(numOfNode, loopPos);
head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));
assertEquals(loopPos, FirstOverlapDetectionGeneral.firstOverlapSlowFastPointerGeneral(head1, head2).value);
numOfNode = 9;
headNodePos = 3;
loopPos = 5;
L = 1;
head1 = createLinkedList1(numOfNode, loopPos);
head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));
FirstOverlapDetectionGeneral.printResult(head1, getHeadNode(head1,loopPos));
FirstOverlapDetectionGeneral.printResult(head2, getHeadNode(head1,loopPos));
assertEquals(headNodePos, FirstOverlapDetectionGeneral.firstOverlapBrutalForce(head1, head2).value);
head1 = createLinkedList1(numOfNode, loopPos);
head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));
assertEquals(headNodePos, FirstOverlapDetectionGeneral.firstOverlapSlowFastPointerGeneral(head1, head2).value);
numOfNode = 2;
headNodePos = 2;
loopPos = 1;
L = 5;
head1 = createLinkedList1(numOfNode, loopPos);
head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));
FirstOverlapDetectionGeneral.printResult(head1, getHeadNode(head1,loopPos));
FirstOverlapDetectionGeneral.printResult(head2, getHeadNode(head1,loopPos));
assertEquals(loopPos, FirstOverlapDetectionGeneral.firstOverlapBrutalForce(head1, head2).value);
head1 = createLinkedList1(numOfNode, loopPos);
head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));
assertEquals(loopPos, FirstOverlapDetectionGeneral.firstOverlapSlowFastPointerGeneral(head1, head2).value);
numOfNode = 1;
headNodePos = 1;
loopPos = 1;
L = 5;
head1 = createLinkedList1(numOfNode, loopPos);
head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));
FirstOverlapDetectionGeneral.printResult(head1, getHeadNode(head1,loopPos));
FirstOverlapDetectionGeneral.printResult(head2, getHeadNode(head1,loopPos));
assertEquals(headNodePos, FirstOverlapDetectionGeneral.firstOverlapBrutalForce(head1, head2).value);
head1 = createLinkedList1(numOfNode, loopPos);
head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));
assertEquals(headNodePos, FirstOverlapDetectionGeneral.firstOverlapSlowFastPointerGeneral(head1, head2).value);
numOfNode = 15;
head1 = createLinkedList1(numOfNode, loopPos);
FirstOverlapDetectionGeneral.printResult(head1, getHeadNode(head1,loopPos));
FirstOverlapDetectionGeneral.printResult(head1, getHeadNode(head1,loopPos));
assertEquals(headNodePos, FirstOverlapDetectionGeneral.firstOverlapBrutalForce(head1, head1).value);
head1 = createLinkedList1(numOfNode, loopPos);
assertEquals(headNodePos, FirstOverlapDetectionGeneral.firstOverlapSlowFastPointerGeneral(head1, head1).value);
}
@Test
public void testOverlapNoLoops() {
System.out.println("testOverlapNoLoops");
int numOfNode = 5;
int headNodePos = 2;
int loopPos = -1;
int L = 3;
LNode head1 = createLinkedList1(numOfNode, loopPos);
LNode head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));
FirstOverlapDetectionGeneral.printResult(head1, getHeadNode(head1,loopPos));
FirstOverlapDetectionGeneral.printResult(head2, getHeadNode(head1,loopPos));
assertEquals(headNodePos, FirstOverlapDetectionGeneral.firstOverlapBrutalForce(head1, head2).value);
head1 = createLinkedList1(numOfNode, loopPos);
head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));
assertEquals(headNodePos, FirstOverlapDetectionGeneral.firstOverlapSlowFastPointerGeneral(head1, head2).value);
numOfNode = 9;
headNodePos = 5;
loopPos = -1;
L = 1;
head1 = createLinkedList1(numOfNode, loopPos);
head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));
FirstOverlapDetectionGeneral.printResult(head1, getHeadNode(head1,loopPos));
FirstOverlapDetectionGeneral.printResult(head2, getHeadNode(head1,loopPos));
assertEquals(headNodePos, FirstOverlapDetectionGeneral.firstOverlapBrutalForce(head1, head2).value);
head1 = createLinkedList1(numOfNode, loopPos);
head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));
assertEquals(headNodePos, FirstOverlapDetectionGeneral.firstOverlapSlowFastPointerGeneral(head1, head2).value);
numOfNode = 9;
headNodePos = 3;
loopPos = -1;
L = 1;
head1 = createLinkedList1(numOfNode, loopPos);
head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));
FirstOverlapDetectionGeneral.printResult(head1, getHeadNode(head1,loopPos));
FirstOverlapDetectionGeneral.printResult(head2, getHeadNode(head1,loopPos));
assertEquals(headNodePos, FirstOverlapDetectionGeneral.firstOverlapBrutalForce(head1, head2).value);
head1 = createLinkedList1(numOfNode, loopPos);
head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));
assertEquals(headNodePos, FirstOverlapDetectionGeneral.firstOverlapSlowFastPointerGeneral(head1, head2).value);
numOfNode = 2;
headNodePos = 2;
loopPos = -11;
L = 5;
head1 = createLinkedList1(numOfNode, loopPos);
head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));
FirstOverlapDetectionGeneral.printResult(head1, getHeadNode(head1,loopPos));
FirstOverlapDetectionGeneral.printResult(head2, getHeadNode(head1,loopPos));
assertEquals(headNodePos, FirstOverlapDetectionGeneral.firstOverlapBrutalForce(head1, head2).value);
head1 = createLinkedList1(numOfNode, loopPos);
head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));
assertEquals(headNodePos, FirstOverlapDetectionGeneral.firstOverlapSlowFastPointerGeneral(head1, head2).value);
numOfNode = 1;
headNodePos = 1;
loopPos = -1;
L = 5;
head1 = createLinkedList1(numOfNode, loopPos);
head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));
FirstOverlapDetectionGeneral.printResult(head1, getHeadNode(head1,loopPos));
FirstOverlapDetectionGeneral.printResult(head2, getHeadNode(head1,loopPos));
assertEquals(headNodePos, FirstOverlapDetectionGeneral.firstOverlapBrutalForce(head1, head2).value);
head1 = createLinkedList1(numOfNode, loopPos);
head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));
assertEquals(headNodePos, FirstOverlapDetectionGeneral.firstOverlapSlowFastPointerGeneral(head1, head2).value);
numOfNode = 15;
head1 = createLinkedList1(numOfNode, loopPos);
FirstOverlapDetectionGeneral.printResult(head1, getHeadNode(head1,loopPos));
FirstOverlapDetectionGeneral.printResult(head1, getHeadNode(head1,loopPos));
assertEquals(headNodePos, FirstOverlapDetectionGeneral.firstOverlapBrutalForce(head1, head1).value);
head1 = createLinkedList1(numOfNode, loopPos);
assertEquals(headNodePos, FirstOverlapDetectionGeneral.firstOverlapSlowFastPointerGeneral(head1, head1).value);
}
@Test
public void testNull() {
LNode head1 = null;
LNode head2 = null;
assertTrue(FirstOverlapDetectionGeneral.firstOverlapBrutalForce(head1, head2) == null);
head1 = null;
head2 = null;
assertTrue(FirstOverlapDetectionGeneral.firstOverlapSlowFastPointerGeneral(head1, head2) == null);
head1 = new LNode(0, null);
head2 = null;
assertTrue(FirstOverlapDetectionGeneral.firstOverlapBrutalForce(head1, head2) == null);
head1 = new LNode(0, null);
head2 = null;
assertTrue(FirstOverlapDetectionGeneral.firstOverlapSlowFastPointerGeneral(head1, head2) == null);
head2 = new LNode(0, null);
head1 = null;
assertTrue(FirstOverlapDetectionGeneral.firstOverlapBrutalForce(head1, head2) == null);
head2 = new LNode(0, null);
head1 = null;
assertTrue(FirstOverlapDetectionGeneral.firstOverlapSlowFastPointerGeneral(head1, head2) == null);
}
}
