CareerCup 150

C.C 2.6

/**
 * 2.6 Given a circular linked list, implement an algorithm which returns the
 * node at the beginning of the loop.
 *
 * DEFINITION Circular linked list: A (corrupt) linked list in which a node's
 * next pointer points to an earlier node, so as to make a loop in the linked
 * list.
 *
 * EXAMPLE Input:A ->B->C->D->E-> C[thesameCasearlier]
 *
 * Output:C
 *
 * @author Jiateng
 */
public class CC2_6 {

    //Time O(n), Space O(1)
    public static int circleNode(ListNode head) {

        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.getNext() != null) {
            fast = fast.getNext().getNext();
            slow = slow.getNext();
            //meet at the start of the circle
            if (slow == fast) {
                break;
            }
        }

        //if no meet
        if (fast == null || fast.getNext() == null) {
            return 0;
        }

        //if meet, change all fast and slow to one step move at one time
        slow = head;
        while (slow != fast) {
            slow = slow.getNext();
            fast = fast.getNext();
        }

        return fast.getVal();
    }

    public static void main(String[] args) {

        //{1-2-3-4-5-3}
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = head.next.next;
        //expect 3
        System.out.println(circleNode(head));
    }
}