代码随想录刷题day14(1)|（链表篇）142.环形链表 II
目录
一、链表理论基础
二、环形链表思路
1.如何判断有环？
2.如何找出环的入口？
3.其他疑问
三、相关算法题目
四、总结
一、链表理论基础
代码随想录 (programmercarl.com)
二、环形链表思路
1.如何判断有环？
使用快慢指针法，定义一个快指针fast，一个慢指针slow，快指针一次移动两步，慢指针一次移动一步，如果快慢指针能够相遇，则说明有环的存在，如果没有相遇，则说明没有环的存在；
快指针一次移动两步，如果有环，一定是快指针先进入环，当快指针在环内走过数圈以后，慢指针进入环，所以相遇一定会发生在环内；
因为快指针相对于慢指针来说，一次是移动一步，所以快慢指针一定会相遇（如果有环的话），而不会出现快指针将慢指针略过的情况；
2.如何找出环的入口？
假设从头结点到环形入口节点 的节点数为x。 环形入口节点到fast指针与slow指针相遇节点 节点数为y。 从相遇节点再到环形入口节点节点数为 z。 如图所示：（图源代码随想录）
那么根据相遇时，slow和fast走过的结点数，可以进行如下推导：
当n=1时，x = z；代表 快指针在环中走了一圈后，快慢指针相遇，此时x = z，那么相交的点就可以这样求：定义指针index1，初始指向链表头节点，定义指针index2，初始指向快慢指针相遇的结点，两个指针同时移动，每次移动一步，当两者相遇时，此时所指位置就是环的入口处；
当n=100或者其他值时，也是相同的求法，区别在于，此时快指针在环中走过的圈数不同而已；
3.其他疑问
1.为什么slow指针在第一圈就会和快指针相遇，而不是也绕环几圈（为什么slow ≠ x+y+k(y+z)）？
A：首先fast指针先进入环，当fast指针走到环中某个位置时，slow指针开始进入环，假设slow指针绕环一圈，由于fast指针走的步数是slow的两倍，那么fast指针走过的路程数一定是大于slow指针走过的路程数（也就是环的一圈），而由前面可知，fast指针不会略过slow指针，一定会追上slow指针，所以在slow指针绕环一圈的过程中，一定有某个点，fast指针追上了slow指针，两者相遇，所以相遇一定发生在slow指针绕环第一圈的过程中，详可见下图：
三、相关算法题目
142.环形链表 II
142. 环形链表 II - 力扣（LeetCode）
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
fast = fast .next.next;//
slow = slow.next;
if(fast == slow){
//此时链表中有环
ListNode index1 = head;//index1指向链表头节点
ListNode index2 = fast;//index2指向快慢指针相遇处 =slow也可以
// 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口
while(index1 != index2){
index1 = index1.next;
index2 = index2.next;
}
//如果index1 = index2 即环的入口处
return index1;
}
}
return null;
}
}四、总结
1.如何判断链表中是否有环？
2.如有环，怎样找出环的入口处，具体思想是？