FirstOverlapDetectionTest.java

import static org.junit.Assert.assertTrue;

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class FirstOverlapDetectionTest {

    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);

        

        FirstOverlapDetection.printResult(head1);

        FirstOverlapDetection.printResult(head2);

        assertEquals(null, FirstOverlapDetection.firstOverlapBrutalForce(head1, head2));

        

        head1 = createLinkedList1(1);

        head2 = createLinkedList1(1);

        FirstOverlapDetection.printResult(head1);

        FirstOverlapDetection.printResult(head2);

        assertEquals(null, FirstOverlapDetection.firstOverlapSlowFastPointer(head1, head2));

        

        head1 = createLinkedList1(10);

        head2 = createLinkedList1(9);

        FirstOverlapDetection.printResult(head1);

        FirstOverlapDetection.printResult(head2);

        assertEquals(null, FirstOverlapDetection.firstOverlapCommonTail(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));

        

        FirstOverlapDetection.printResult(head1);

        FirstOverlapDetection.printResult(head2);

        assertEquals(headNodePos, FirstOverlapDetection.firstOverlapBrutalForce(head1, head2).value);

        

        head1 = createLinkedList1(numOfNode);

        head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));

        assertEquals(headNodePos, FirstOverlapDetection.firstOverlapSlowFastPointer(head1, head2).value);

        

        head1 = createLinkedList1(numOfNode);

        head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));

        assertEquals(headNodePos, FirstOverlapDetection.firstOverlapCommonTail(head1, head2).value);

        

        numOfNode = 9;

        headNodePos = 3;

        L = 1;

        head1 = createLinkedList1(numOfNode);

        head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));

        

        FirstOverlapDetection.printResult(head1);

        FirstOverlapDetection.printResult(head2);

        assertEquals(headNodePos, FirstOverlapDetection.firstOverlapBrutalForce(head1, head2).value);

        

        head1 = createLinkedList1(numOfNode);

        head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));

        assertEquals(headNodePos, FirstOverlapDetection.firstOverlapSlowFastPointer(head1, head2).value);

        

        head1 = createLinkedList1(numOfNode);

        head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));

        assertEquals(headNodePos, FirstOverlapDetection.firstOverlapCommonTail(head1, head2).value);

        

        numOfNode = 2;

        headNodePos = 2;

        L = 5;

        head1 = createLinkedList1(numOfNode);

        head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));

        

        FirstOverlapDetection.printResult(head1);

        FirstOverlapDetection.printResult(head2);

        assertEquals(headNodePos, FirstOverlapDetection.firstOverlapBrutalForce(head1, head2).value);

        

        head1 = createLinkedList1(numOfNode);

        head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));

        assertEquals(headNodePos, FirstOverlapDetection.firstOverlapSlowFastPointer(head1, head2).value);

        

        head1 = createLinkedList1(numOfNode);

        head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));

        assertEquals(headNodePos, FirstOverlapDetection.firstOverlapCommonTail(head1, head2).value);

        

        numOfNode = 1;

        headNodePos = 1;

        L = 5;

        head1 = createLinkedList1(numOfNode);

        head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));

        

        FirstOverlapDetection.printResult(head1);

        FirstOverlapDetection.printResult(head2);

        assertEquals(headNodePos, FirstOverlapDetection.firstOverlapBrutalForce(head1, head2).value);

        

        head1 = createLinkedList1(numOfNode);

        head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));

        assertEquals(headNodePos, FirstOverlapDetection.firstOverlapSlowFastPointer(head1, head2).value);

        

        head1 = createLinkedList1(numOfNode);

        head2 = createLinkedList2(L, getHeadNode(head1, headNodePos));

        assertEquals(headNodePos, FirstOverlapDetection.firstOverlapCommonTail(head1, head2).value);

        

        numOfNode = 15;

        

        FirstOverlapDetection.printResult(head1);

        FirstOverlapDetection.printResult(head1);

        assertEquals(headNodePos, FirstOverlapDetection.firstOverlapBrutalForce(head1, head1).value);

        

        head1 = createLinkedList1(numOfNode);

        assertEquals(headNodePos, FirstOverlapDetection.firstOverlapSlowFastPointer(head1, head1).value);

        

        head1 = createLinkedList1(numOfNode);

        assertEquals(headNodePos, FirstOverlapDetection.firstOverlapCommonTail(head1, head1).value);

    }

    

    @Test

    public void testNull() {

        LNode head1 = null;

        LNode head2 = null;

        assertTrue(FirstOverlapDetection.firstOverlapBrutalForce(head1, head2) == null);

        head1 = null;

        head2 = null;

        assertTrue(FirstOverlapDetection.firstOverlapSlowFastPointer(head1, head2) == null);

        head1 = null;

        head2 = null;

        assertTrue(FirstOverlapDetection.firstOverlapCommonTail(head1, head2) == null);

        

        head1 = new LNode(0, null);

        head2 = null;

        assertTrue(FirstOverlapDetection.firstOverlapBrutalForce(head1, head2) == null);

        head1 = new LNode(0, null);

        head2 = null;

        assertTrue(FirstOverlapDetection.firstOverlapSlowFastPointer(head1, head2) == null);

        head1 = new LNode(0, null);

        head2 = null;

        assertTrue(FirstOverlapDetection.firstOverlapCommonTail(head1, head2) == null);

        

        head2 = new LNode(0, null);

        head1 = null;

        assertTrue(FirstOverlapDetection.firstOverlapBrutalForce(head1, head2) == null);

        head2 = new LNode(0, null);

        head1 = null;

        assertTrue(FirstOverlapDetection.firstOverlapSlowFastPointer(head1, head2) == null);

        head2 = new LNode(0, null);

        head1 = null;

        assertTrue(FirstOverlapDetection.firstOverlapCommonTail(head1, head2) == null);

    }

}