剑指offer之链表中环的入口结点
题目描述
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
要求不能使用额外的空间。
解题思路
使用双指针，一个指针fast每次移动两个节点，一个指针slow每次移动一个节点。
因为存在环，所以两个指针必定相遇在环中的某个节点上。
假设相遇点在下图的 z1 位置，此时 fast 移动的节点数为 x+2y+z，slow 为 x+y，
由于 fast 速度比 slow 快一倍，因此 x+2y+z=2(x+y)，得到 x=z。
在相遇点，slow 要到环的入口点还需要移动 z 个节点，如果让 fast 重新从头开始移动，并且速度变为每次移动一个节点，那么它到环入口点还需要移动 x 个节点。
在上面已经推导出 x=z，因此 fast 和 slow 将在环入口点相遇。
解题代码
public static void main(String[] args) {
public ListNode EntryNodeOfLoop(ListNode pHead) {
if(pHead.next == null || pHead.next.next == null)
return null;
ListNode slow = pHead.next;
ListNode fast = pHead.next.next;
while(fast != null){
if(fast == slow){
fast = pHead;
while(fast != slow){
fast = fast.next;
slow = slow.next;
}
return fast;
}
slow = slow.next;
fast = fast.next.next;
}
return null;
}
}