Site Search:

OverlapDetectionTest.java


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

}