142. 环形链表 II

力扣题目链接

做不出来

想半天都不行

怎么判断有环

首先需要想清楚，用什么办法才能明确知道链表出现重合段？另外一道题里面靠的就是让两个指针走，如果方向两个指针指向的是同一个结点，那就是出现了重合。这一道题也得这么做。

但是怎么让两个指针在入口处相遇呢？这是很难做到的，问题出在想让指针在入口处相遇。因为这道题的这个入口定位难度显然比另外一道要高的多，另外一个可以依据入口后所有结点都相同，让尾部对齐就能定位到入口。但是这里这个环你不知道，没办法搞。

那么怎么办？不要立刻找到那个入口，这太难了。先判断链表有没有环。所以现在我们知道的就是：2个指针、借助指针指向系相同来判断存在环。两个指针什么时候释放？因为进入环以后没有什么明确的特征，来指示另外一个指针什么时候释放，所以只能同时释放。但是两个指针速度一样，一定是指向同一个结点，那有什么意义？对，没意义，所以，速度不能一样！这就来到了本题的核心：快慢指针，差在移动速度上，每一次快指针都比慢指针多移动。如果有环，快慢指针最终都会进入环里绕圈。因为速度差异，就是一个小学圆形操场追及问题（？）。让快指针每次走2步，慢指针每次走1步，快指针就相对于慢指针以1步/次的速度接近，一定会在环里追上慢指针，并指向同一个节点，这样就出现了一个明确的判据。如果没有环，快指针会碰到链表的结尾null，转不起圈，结束。

怎么找到入口？

上面的方法成功实现了0到1的突破，已经可以判断链表有没有环了。但是找入口的问题还是没有解决，这个入口的特征仍然不明显。于是需要进行一些数学推理，我只能说，第一个想到这个的还是比较逆天的： 设，$x$是入口前的步数，$y$是入口到相遇的步数，$z$是这一圈剩下的，从相遇再回到入口的步数。注意$xyz$是间隔数量，而不是结点数量，这与指针走几步直接相关，不是结点数量。这个环一圈就是y+z步。

在刚才的追及中，slow到达相遇点走了$x+y$步。为什么slow一定是一圈没走完就被追上？因为fast的速度是2倍，slow走1圈fast就走2圈，不论如何都一定会碰上。fast到达相遇点走了$x+y+n(y+z)$。为什么有个$n$？不是$1$？因为不知道$x$有多少长，在fast进了环内以后，不知道这个slow在$x$这一段留了多久。$n$一定是大于等于$1$的，总不可能fast和slow走的步数一样。

那么根据速度关系，能列出

$$2(x+y)=x+y+n(y+z)$$

化简可得

$$x=(n-1)(y+z)+z$$

我们知道，$(y+z)$是一圈的路程。于是你发现，$x$这一段路程等于$n-1$个一圈的全程加上相遇点到入口剩下的路。

这代表着，如果让2个指针分别从链表起点和刚才的相遇点同时出发，两个指针最后会在入口处相遇！这样就能找到入口结点！

于是本道题结束。

代码

class Solution {
  public:
	ListNode *detectCycle(ListNode *head)
	{
		ListNode *fast = head, *slow = head;
		while (fast != nullptr && fast->next != nullptr) {
			fast = fast->next->next;
			slow = slow->next;
			if (fast == slow) { // 有环
				ListNode *p1 = head, *p2 = fast;
				while (p1 != p2) {
					p1 = p1->next;
					p2 = p2->next;
				}
				return p1;
			}
		}
		// 无环
		return nullptr;
	}
};

稍微注意一下fast != nullptr && fast->next != nullptr，这是因为fast一次走2步，要看好2个都不是null才能走。