找到环状子链表的入口

2020-07-20

整体思路：
我们通过构造两次相遇来解决这个问题，首先我们要用双指针fast和slow来辅助解题，我们将两个指针的初始位置都指向头节点，然后fast一次走两步，slow一次走一步，这里分为两种情况:
第一种情况:fast直接到达了链表的尾部，那么是不含有环状结构的，直接return fasle
第二种情况:根据运动员的例子我们可以得知如果含有环状结构那么fast和slow是一定会相遇的，这里我们来分析以下fast和slow走过的路程，首先fast走的路程一定是slow的2倍，所以f = 2s①，然后fast比slow多走了n圈，所以f=s+nb②，联立①和②我们可以得出f=2nb,s=nb，这是第一次相遇时，f和s走的总路程。
根据第二种情况继续分析：此时我们记录总共走的步数为k，那么指针走到环状链表的入口时，k=a+nb,a为head到入口的距离，而此时s走的总路程是nb,所以如果我们s继续走a步就可以使s到达入口处，但我们不知道a的值

为了求a我们构造第二次相遇:所以此时我们令fast指向head，两者一同以相同速度走，那么fast走a步到了入口，s同样到了入口，所以当fast和slow相遇时，就是入口

public class Solution {
   	public ListNode detectCycle(ListNode head) {
		if(head == null||head.next == null) {
			return null;
		}
		ListNode slow = head;
		ListNode fast = head;
		//构建第一次相遇
		while(true) {
			if(fast==null||fast.next==null) {
				return null;
			}
			slow = slow.next;
			fast = fast.next.next;
			if(fast == slow) {
				break;
			}
		}
		//构建第二次相遇
		fast = head;
		while(slow!=fast) {
			slow = slow.next;
			fast = fast.next;
		}
		return slow;
	}
}