Site Search:

LoopDetectionSolutionOneTest.java


import static org.junit.Assert.*;

import org.junit.Test;

public class LoopDetectionSolutionOneTest {

    private LNode createLinkedList(int numOfNode, int headNodePos) {
        LNode head = new LNode(0, null);
        LNode current = new LNode(1, null);
        
        LNode loopHead = null;
        if(headNodePos == 1) loopHead = current;
        head.next = current;
        for(int i = 2; i <= numOfNode; i++) {
            current.next = new LNode(i, null);
            current = current.next;
            if(i == headNodePos) {
                loopHead = current;
            }
        }
        current.next = loopHead;
        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 testLoop() {
        
        int numOfNode = 5;
        int headNodePos = 2;
        LNode head = createLinkedList(numOfNode, headNodePos);
        LoopDetectionSolutionOne.printResult(head, getHeadNode(head, headNodePos));
        assertTrue(LoopDetectionSolutionOne.hasLoopBrutalForce(head));
        assertTrue(LoopDetectionSolutionOne.hasLoopSlowFastPointer(head));
        
        numOfNode = 5;
        headNodePos = 5;
        head = createLinkedList(numOfNode, headNodePos);
        LoopDetectionSolutionOne.printResult(head, getHeadNode(head, headNodePos));
        assertTrue(LoopDetectionSolutionOne.hasLoopBrutalForce(head));
        assertTrue(LoopDetectionSolutionOne.hasLoopSlowFastPointer(head));
        
        numOfNode = 5;
        headNodePos = 1;
        head = createLinkedList(numOfNode, headNodePos);
        LoopDetectionSolutionOne.printResult(head, getHeadNode(head, headNodePos));
        assertTrue(LoopDetectionSolutionOne.hasLoopBrutalForce(head));
        assertTrue(LoopDetectionSolutionOne.hasLoopSlowFastPointer(head));
        
        numOfNode = 1;
        headNodePos = 1;
        head = createLinkedList(numOfNode, headNodePos);
        LoopDetectionSolutionOne.printResult(head, getHeadNode(head, headNodePos));
        assertTrue(LoopDetectionSolutionOne.hasLoopBrutalForce(head));
        assertTrue(LoopDetectionSolutionOne.hasLoopSlowFastPointer(head));
        
        numOfNode = 7;
        headNodePos = 5;
        head = createLinkedList(numOfNode, headNodePos);
        LoopDetectionSolutionOne.printResult(head, getHeadNode(head, headNodePos));
        assertTrue(LoopDetectionSolutionOne.hasLoopBrutalForce(head));
        assertTrue(LoopDetectionSolutionOne.hasLoopSlowFastPointer(head));
        
        numOfNode = 800;
        headNodePos = 3;
        head = createLinkedList(numOfNode, headNodePos);
        LoopDetectionSolutionOne.printResult(head, getHeadNode(head, headNodePos));
        assertTrue(LoopDetectionSolutionOne.hasLoopBrutalForce(head));
        assertTrue(LoopDetectionSolutionOne.hasLoopSlowFastPointer(head));
    }
    
    @Test
    public void testNoLoop() {
        
        int numOfNode = 5;
        int headNodePos = 0;
        LNode head = createLinkedList(numOfNode, headNodePos);
        LoopDetectionSolutionOne.printResult(head, getHeadNode(head, headNodePos));
        assertFalse(LoopDetectionSolutionOne.hasLoopBrutalForce(head));
        assertFalse(LoopDetectionSolutionOne.hasLoopSlowFastPointer(head));
        
        numOfNode = 1;
        headNodePos = 0;
        head = createLinkedList(numOfNode, headNodePos);
        LoopDetectionSolutionOne.printResult(head, getHeadNode(head, headNodePos));
        assertFalse(LoopDetectionSolutionOne.hasLoopBrutalForce(head));
        assertFalse(LoopDetectionSolutionOne.hasLoopSlowFastPointer(head));
        
        numOfNode = 7;
        headNodePos = 0;
        head = createLinkedList(numOfNode, headNodePos);
        LoopDetectionSolutionOne.printResult(head, getHeadNode(head, headNodePos));
        assertFalse(LoopDetectionSolutionOne.hasLoopBrutalForce(head));
        assertFalse(LoopDetectionSolutionOne.hasLoopSlowFastPointer(head));
        
        numOfNode = 800;
        headNodePos = 0;
        head = createLinkedList(numOfNode, headNodePos);
        LoopDetectionSolutionOne.printResult(head, getHeadNode(head, headNodePos));
        assertFalse(LoopDetectionSolutionOne.hasLoopBrutalForce(head));
        assertFalse(LoopDetectionSolutionOne.hasLoopSlowFastPointer(head));
    }
    
    @Test
    public void testNull() {
        LNode head = null;
        LoopDetectionSolutionOne.printResult(head, null);
        assertFalse(LoopDetectionSolutionOne.hasLoopBrutalForce(head));
        assertFalse(LoopDetectionSolutionOne.hasLoopSlowFastPointer(head));
        
        head = new LNode(0, new LNode(1, null));
        LoopDetectionSolutionOne.printResult(head, null);
        assertFalse(LoopDetectionSolutionOne.hasLoopBrutalForce(head));
        assertFalse(LoopDetectionSolutionOne.hasLoopSlowFastPointer(head));
    }

}