DetectCycleStartInList.java

// in this context, we've already know that the list has cycle
// suppose there is a class Node 
// public class Node<Item>{
//     Item item;
//     Node next;
// }
// import the Node class here;
public class DetectCycleStartInList{// I wish I could use a better name :)
    
    
    public Node detect(Node head){
        if (head == null) return null;
        Node slowRunner = head; // move at rate 1
        Node fastRunner = head; // move at rate 2
        
        while(true){
            fastRunner = fastRunner.next.next;
            slowRunner = slowRunner.next;
            if (slowRunner == fastRunner) break;
        }
        
        while(true){
            slowRunner = slowRunner.next;
            head = head.next;
            if (slowRunner == head) break;
        }
        return slowRunner;
    }
}