[LeetCode]Linked List Cycle II

[LeetCode]Linked List Cycle II

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?

所以有a+b = nr； 進一步有 b+ pr = （r-a）+qr，即從頭指針和當前相遇位置的指針以相同速度移動一定在環口位置相遇

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
	public ListNode detectCycle(ListNode head) {
		if(head==null) return null;
		ListNode slow2 = head;
		ListNode slow = head;
		ListNode fast = head;
		boolean isCycle = false;
		while(fast!=null&&fast.next!=null){
			slow = slow.next;
			fast = fast.next.next;			
			if(slow == fast) {
				isCycle =  true;
				break;
			}
		}
		if(isCycle){
			while(slow2!=slow){
				slow = slow.next;
				slow2 = slow2.next;
			}
			return slow;
		}else{
			return null;
		}
	}
}