有关于链表，我们总会遇到关于其的各类问题，像反转链表，双向链表，有环链表等，今天，我们就有环链表展开细说。
1.判断链表有环
如果有一个单向链表，且链表中可能出现“环”，那么，该如何用程序来判断该链表是否为有环链表?
方法一：也是最简单粗暴的方法，从头节点开始，依次遍历单链表中的每一个节点。每遍历一次新节点，就与之前所有节点进行比较，如果某个节点被遍历两次，则为有环。(时间复杂度为O(n²),空间复杂度为O(1))。
方法二：创建一个哈希表，以节点的id为key值的哈希表，存储曾经便利过的节点，在依次遍历整个链表，如果遍历的节点为新节点，那就记录在哈希表，当遍历发现在哈希表内部遍历过，证明链表有环。(使用了哈希表作为额外缓存，该解法时间复杂度为O(n),空间复杂度为O(n))。
方法三：利用双指针法.创建两个指针p1,p2使它们同时指向链表的头节点，使p1 = head -> next; p2 = head -> next ->next;(即使p1速度为1，p2速度为2)。
1.p1,p2指向节点5
2.p1指向3，p2指向7
3.p1保持速度1，p2保持速度2，如果有环，则速度快的一定会追上速度慢的，当p1 == p2时证明了链表有环
下面为部分代码实现：
//部分代码 bool isCycle(ListNode *Head) { ListNode* p1 = head;//设置双指针指向头节点 ListNode* p2 = head; while (p2 != NULL && p2->next != NULL) { p1 = p1->next;//设置p1速度为1 p2 = p2->next->next;//设置p2速度为2 if (p1 == p2) { return ture;//p1 == p2表示两指针相遇，为有环链表 } } return false;//双指针不相遇，不是有环链表 }
2.获取有环链表的环长以及入环点
1.求有环链表的环长
当两个指针首次相遇，证明链表有环的时候，让两个指针从相遇点继续循环前进，统计前进次数，直到第二次相遇，此时统计出来的次数就是环长，因为p1速度为1，p2速度为2，则再次相遇的时候，p2比p1多走了一圈，统计出来前进的次数就为环长。
int isCycle(ListNode *Head) { ListNode* p1 = head; ListNode* p2 = head; static int count = 0;//记录前进次数 while (p2 != NULL && p2->next != NULL)//第一个循环先使得p1 、 p2 处于第一次相遇的位置 { p1 = p1->next; p2 = p2->next->next; if (p1 == p2) { break; } } while (p2 != NULL && p2->next != NULL) { p1 = p1->next; p2 = p2->next; count++; if (p1 == p2) { break;//第二次相遇时终止循环 } } return count;//将记录的前进次数返回 }
2.求有环链表的入环点
假设从链表头节点到入环点的距离是D，从入环点到两个指针首次相遇点的距离为S1, 从首次相遇点到入环点的距离为S2。
分析：当第一次相遇时，指针P1一次只走一步, 所走的距离为D + S1。指针P2一次走2步， 多走了n(n >= 1) 圈， 所以走的距离为D + S1 + n(S1 + S2)。
则2(D + S1) = D + S1 + n(S1 + S2)
则D = (n - 1)(S1 + S2) + S2
也就是说，从链表头节点到入环点的距离，等于从首次相遇点绕环n - 1 圈在回到入环点的距离
则此时， 把其中任意一个指针放回到头节点，并且保持速度都为1，则他们最终相遇的节点就是入环点。
ListNode* detectCycle(ListNode* head) { ListNode* p = head, * q = head; while (q && q->next) {//当q 与 q 的下一个节点不为空则执行循环 p = p->next; q = q->next->next; if (q == p) break;//到达首次相遇点时停止 } if (q == NULL || q->next == NULL) return NULL; p = head; while (p != q) {//直到再次相遇时停止循环 p = p->next; q = q->next; } return p;//返回p或q节点都是入环节点 }
OK,有环链表的问题今天就介绍到这里啦，主要对有环链表的入环点，环长，以及判断是否存在环（前两个例子我就不敲了，理解就好）希望对你有所帮助，学无止境，我们一起加油一起学习，也祝各位小伙伴们学业有成，早日进入自己心仪的大厂！
![[java刷算法]牛客—剑指offer链表有环的入口、反转链表、合并排序链表](https://ucc.alicdn.com/images/user-upload-01/8b3cf078d5094698a53196a3eb756516.png?x-oss-process=image/resize,h_160,m_lfit)
