力扣 142 环形链表Ⅱ

给定一个链表的头节点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或者链表中的一个有效索引

这道题跟着逻辑走思路很清晰，但实际上需要严谨证明和反复琢磨才能真正理解并独立解题

主要解决两点：

1. 判断链表是否成环
2. 如果有环，那么环的入口在哪里

一. 是否成环？

这里可以采用双指针，分别定义快慢指针，均从头节点出发，其中fast每次移动两个节点，而slow每次移动一个节点，如果fast和slow在移动途中相遇，说明该链表成环。

为什么快慢指针相遇就说明成环？

因为是快指针先入环，慢指针后入环，如果fast指针和slow指针相遇的话，一定是在环中相遇，在环内相遇就说明肯定成环了。

为什么有环一定会相遇？

本质上是因为两指针存在速度差，在环内绕环移动时，快指针一定会追上慢指针。这是因为fast走两步，slow走一步，对slow来说fast是一点一点接近它的，所以两者一定会在环内某一节点处相遇。

画一个环，让fast在任意一个节点开始追赶slow，会发现展开后都是下图这种情况：

此时，按照定义fast往前走一次两步，slow走一次一步，两者就会在 3 处相遇。

完整动画演示如下图：

二. 入口在哪里？

假设从头结点到入口节点的节点数为x，入口节点到两指针相遇节点的节点数为y，从相遇节点再到入口节点的节点数为z， 如图所示：

slow指针走过的节点数为x + y，fast指针走过的节点数为x + y + n * (y + z)
其中n表示快指针追慢指针的过程中绕过的圈数。

由于快指针一次走两个节点，慢指针一次走一个，故快指针走过的节点数是慢指针的2倍。
也就是2 * (x + y) = x + y + n * (y + z)，两边消一个x + y化简得x + y = n * (y + z)。

要找到是环形入口节点，也就是x，所以把x提出来放左边得x = n * (y + z) - y。右边提一个y + z出来化简得x = (y + z) * (n - 1) + z。

化简到这一步，不妨设环绕圈数n为1，即可得x = z。这也就是说，从头结点和相遇节点同时出发一个指针，两个指针每次只走一个节点， 那么当这两个指针相遇时所在处就是环形入口的节点。

那么**n如果大于1** 是什么情况呢，其实这种情况和n为1的时候是一样的，一样可以通过这个方法找到入口节点，只不过index1指针在环里多转了(n-1)圈，然后再遇到index2，相遇点依然是环形的入口节点。

至此，我们完成了一开始提出的两个问题！

✅下面是完整力扣代码：

class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode* fast = head; ListNode* slow = head; while(fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; if (slow == fast) { ListNode* index1 = fast; ListNode* index2 = head; while (index1 != index2) { index1 = index1->next; index2 = index2->next; } return index2; } } return nullptr; } };