判断链表是否有环并求环的入口和环的长度

本文主要是介绍判断链表是否有环并求环的入口和环的长度，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

方法：

求链表是否有环，最直观的方法是从头结点的地址开始，把下一个地址都取出来，然后比对，是否有相同的。但这个方法需要两两比较，算法时间复杂度较高。
更好的一个做法是快慢指针（慢指针一次前进一个地址，快指针一次前进两个地址）同时从头结点出发，只有链表有环存在，则它们必定会相遇。
快慢指针算法有一个注意点，慢指针进入环之前，快指针可能已经在环中绕了几次圈了。
首先比较简单的是求环的长度，当快慢指针第一次相遇，可以确定的一点是它们一定都在环中，那么按照它们原先的速度绕圈，当第二次相遇的时候，环的长度就出来了。
求环的入口相对比较难想到，要分段来求，(假设 a 是从头结点到环入口，r是环周长)
A. 假设慢指针刚刚到达环入口，此时快指针在距离环入口 x 处。这一点能给到我们的信息是 a = x + nr (n=1,2,3,4)

B. 从这点之后，实际上问题转化成在环上，快指针去追慢指针，而追击的距离变成环的长度，y - x 的距离。由于速度差是1，很明显被追到的时候，慢指针走过y-x的距离，也就是慢指针距离环入口 x 的距离。
C. 从相遇的这个地方开始，慢指针继续走 x + nr ，即 a 的距离，则到达环入口。所以我们只需同时从头指针出发一个慢指针，两者相遇即为环入口。

看完思路可以去实现一波：牛客地址

class Solution {
public:ListNode* EntryNodeOfLoop(ListNode* pHead){ListNode * fast=pHead;ListNode * slow = pHead;//快指针和慢指针在头结点开始跑，第一次相遇停下while(fast != NULL && fast->next != NULL){slow = slow->next;fast = fast->next->next;if(fast == slow) {//第二个慢指针从头结点出发ListNode * slow2 = pHead;while(slow2 != slow) {slow2 = slow2->next;slow = slow->next;}return slow;}}return NULL;}
};