题解 | #链表中环的入口结点#

public ListNode EntryNodeOfLoop(ListNode pHead)
{
//暴力哈希
// HashSet<listnode> hash = new HashSet<listnode>();
// while(pHead!=null)
// {
// if(hash.Contains(pHead)==true)
// return pHead;
// else {
// hash.Add(pHead);
// pHead = pHead.next;
// }
// }
// return null;
//经典快慢指针解法，也是本题一般考察的目的
ListNode slow = pHead;
ListNode fast = pHead;
if(pHead ==null)return null;
bool flag = false;
while(fast!=null && fast.next!=null)//因为是一次走两步，所以要fast.next！=null防止越界
{
slow = slow.next;
fast = fast.next.next;
if(fast == slow)
{
flag = true;
break;//说明存在环
}
}
if(flag == false)return null;//单链表，返回null
//现在，slow跟fast都在相遇点
//由S(fast) = 2S(slow)化简得到公式，可得关系式(具体的自己推导一下)，于是有：
slow = pHead;
while(slow!=fast)
{
slow = slow.next;
fast = fast.next;
}
return slow;
}</listnode></listnode>