Linked List Cycle II @LeetCode

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

	package leetcode.linkedlist;
	/***
	* To be honest, I cannot infer this by mySelf. Just remember the answer.
	*
	* Solution 1: Two meets.
	* After first meet, head and slow move together, next time, that means second time, they meet at Entry.
	*
	* Solution 2: Three meets.
	* After first meet, let slow go and meet fast again, then we get the circle length L.
	* Let them go back head, let one go L steps, and the third time we meet will at Entry.
	*
	* Reference: http://blog.csdn.net/whuwangyi/article/details/14103993 && CC 150
	*
	* @author jeffwan
	* @date Feb 16, 2014
	*/
	public class DetectCycle {
	public ListNode detectCycle(ListNode head) {
	if (head == null) {
	return null;
	}
	ListNode slow, fast;
	slow = fast = head;
	do {
	if (fast.next == null || fast.next.next == null) {
	return null;
	}
	slow = slow.next;
	fast = fast.next.next;
	} while(slow != fast);
	while(head != slow) {
	head = head.next;
	slow = slow.next;
	}
	return head;
	}
	class ListNode {
	int val;
	ListNode next;
	ListNode (int x) { this.val = x; }
	}
	}

view raw DetectCycle.java hosted with ❤ by GitHub