代码随想录二刷 ｜ 链表 ｜环形链表II
题目描述
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
提示：
链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引
进阶：你是否可以使用 O(1) 空间解决此题？
解题思路 & 代码实现
本题主要解决两个问题：
- 判断链表是否有环
- 如果有环如何找到环的入口
判断链表是否有环
使用快慢指针法，分别定义fast和slow两个指针，从头节点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果两个指针在途中相遇，说明这个链表有环。
强调途中的意思是指两个指针不是在链表末尾相遇的。
因为fast指针移动的快，所以如果两个指针相遇，一定是fast追上了slow指针，并且一定是在环中相遇，因为假如不在环中相遇，fast是无法从slow的后面追上slow的。
至于fast为什么走两步，slow为什么走一步，是因为如果存在环，fast相当于是一步一步的追赶slow，也可以想象为slow没有动，fast一次走一步，这样就比较好理解了。
之所以slow也要移动，是因为最终要找的是环的入口，slow如果不移动，环的入口就比较难判断。
如何找到环的入口
假设从头结点到环形入口节点的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点节点数为y。 从相遇节点再到环形入口节点节点数为z。 如图所示：
相遇时，slow指针走过的路程为x + y，fast针走过的路程为x + y + n * (y + z)，n表示fast指针在环内走了 n 圈才遇到slow指针。
因为fast指针的速度是slow指针的两倍，fast指针走的路程是slow指针走的路程的两倍：
x + y + n * (y + z) = 2 * (x + y)
因为要求的是环形入口节点的位置，因此把 x 放在等式左边：
x = n * (y + z) - y
再从其中提取出一个 y + z来：
x = (n - 1) (y + z) + z
当 n = 1时，也就是fast指针只走了一圈时，公式可化简为x = z，这表示如果从头节点出发一个指针，从相遇节点也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候，那个相遇的节点就是环形入口节点。
当n > 1的时候，由于y + z就是环的长度，这表示fast指针在圈内走了一些圈数，最终还是能得出n = 1时的结论。
class Solution{
public:
ListNode* detectCycle(ListNode* head){
ListNode* fast = head;
ListNode* slow = head;
while (fast != NULL && fast -> next != NULL) {
slow = slow -> next; // slow移动一步
fast = fast -> next -> next; // fast移动两步
if (slow == fast) {
// 当 fast 和 slow 相遇时
ListNode* curA = head;
ListNode* curB = fast;
while (curA != curB) {
curA = curA -> next;
curB = curB -> next;
}
return curA; // 找到入口节点
}
}
return NULL:
}
};
