leetcode 142. Linked List Cycle II

本来应该是做leetcode 287. Find the Duplicate Number的。但是这题的思路需要用到leetcode 142解题思想。因此，先做142，再去弄明白287的思路，是一个更好的路线。

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

Note: Do not modify the linked list.

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

意思就是一个链表中如果有环，你能找出环开始的那个结点吗？如果没有环，返回null.

思路是这样：使用一个快指针和一个慢指针：快指针一次走2个结点，慢指针一次走1个结点。如果快慢指针能相遇，说明链表中有环。假设是慢节点走了k步之后它们俩相遇，再假设环的长度为r。那么 2k - k=nr，得到 k=nr。
假设”链表的初始结点“和”环的初始结点“之间的距离为s，假设“链表的初始结点”和“两指针的初始相遇结点”之间的距离为k（也就是上述的慢指针走了k步的k），假设“环的初始结点”和“两指针的初始相遇结点”之间的距离为m。那么s=k-m。
那么我们得出s=k-m=nr-m=(n-1)r+(r-m)。我们取n=1（即慢指针和快指针第一次相遇，快指针比慢指针多走了一个环，所以n=1）。这样得到s=r-m。r-m是什么呢？就是下图中我蓝色标出的那部分。接下来，我们再使用两个指针。一个指针指向链表头部，一个指针指向快慢指针相遇的结点。这两个指针一次都走1步。这两个指针第一次相遇时的结点，就是环开始的结点。
下面是图示。（那个环是顺时针方向的）

public ListNode detectCycle(ListNode head) {
	if(head==null||head.next==null){
		return null;
	}
	//k=nr
	//s=k-m=nr-m=(n-1)r+(r-m)
	//s=r-m
	boolean hasCycle=false;
	ListNode fast=head;
	ListNode slow=head;
	while(fast!=null&&fast.next!=null&&slow!=null){
		fast=fast.next.next;
		slow=slow.next;
		if(slow==fast){
			hasCycle=true;
			break;
		}
	}
	if(hasCycle==false){
		return null;
	}
	//现在slow和fast都到达meeting点了
	ListNode pointer1=head;
	ListNode pointer2=slow;
	while(pointer1!=pointer2){
		pointer1=pointer1.next;
		pointer2=pointer2.next;
	}
	return pointer1;
}