题解 | #链表中环的入口结点#
链表中环的入口结点
https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead) {
if(pHead->next==pHead) return pHead; //单个元素成环直接返回头节点
if(pHead->next==NULL) return NULL; //只有一个元素不成环，直接返回null
ListNode* fast=pHead->next->next; //定义快指针一次走两个
ListNode* slow=pHead->next; //定义慢指针一次走一个
while(fast!=slow){ //如果表中有环则二者必定在慢指针走完环一圈前相遇
if(fast==NULL) return NULL; //在fast前进的过程中，只要fast=null，则表明表中无环
fast=fast->next;
if(fast==NULL) return NULL;
fast=fast->next;
slow=slow->next;
}
fast=pHead; //此时快慢指针指向环中的同一个节点，此时令慢指针保存，快指针回到头
while(fast!=slow){ //令快慢指针速度相同往后走，当他们相遇时，就是第一个入环的节点
fast=fast->next;
slow=slow->next;
}
return fast; //此时返回fast或slow都可
}
};
/*
原理解释
考虑表中确实有环的情况，快慢指针首次相遇时，慢指针走过的路程时进环前的a和环内的b
而快指针走过的路程是环前的a+环内的b+除b外剩下环的部分c+第二圈走过的b
而此时快指针走过的路程是慢指针的2倍
所以可以得到a+b+b+c=（a+b）*2 所以a=c，即环前的路程和当前相遇位置再走到环入口的路程相同
所以此时令一个指针回到链表头，二者同速前进到相遇，就恰好是环入口，返回即可。
*/
