CTCI 2.6

Given a circular linked list, implement an algorithm which returns the node at the begining of the loop.

CTCI 2.6.java

/*
            3 4 5 5
            4     1
1 2 3 4 5 6 7 8 9 0
*/

public static Node findBeginningOfCircle(Node root){
    Node fast = root;
    Node slow = root;
    while(fast != null && slow != null){
        fast = fast.next;
        slow = slow.next;
        if(fast != null) fast = fast.next;
        if(fast == slow) break;
    }
    if(fast == null || slow == null) return null;
    
    slow = root;
    while(slow != fast){
        slow = slow.next;
        fast = fast.next;
    }
    
    return slow;
}