环形链表查找入环节点

P. S.：以下代码均在VS2019环境下测试，不代表所有编译器均可通过。 P. S.：测试代码均未展示头文件stdio.h的声明，使用时请自行添加。

问题展示

在这里插入图片描述

一. 前言

在我的前一篇博客中已经分析过如何判断链表是否带环，如需了解请直达

链表带环问题之判断链表是否带环

下面我们来了解一下如何查找到链表的入环点。

二. 查找入环节点

2.1. 查找方法

我们不再对判断链表是否带环进行讨论，我们直接快进到快慢指针已经在环中相遇的时间节点：

在这里插入图片描述
如有不解请查看：
链表带环问题之判断链表是否带环

在此基础上，我们指定一个 point 代表我们查找的入环节点，让 point 指向链表的开头，再此基础上我们让 point 和 slow 以同样的速率进行前进，也就是每次前进一个节点。
在这里插入图片描述
当 point 和 slow 相遇时，point 指向的就是入环的节点。

2.2. 解析

在上述解决办法中，我们通过让 point 指针和 slow 指针同时以相同速率位移得到入环节点，那其中的原理是什么呢？
下面我将逐步解析：
首先是 fast 与 slow 走过的路程：
在上述办法中，开始时我们让 fast 和 slow 以 2：1的速率进行前行，假设 slow 刚刚到达环节点，此时我们记 slow 走过的路程为 L，如下图所示：

在这里插入图片描述而此时我们假设fast已经在环内走了 x 圈，假设一圈大小为 C ，并且此时 fast 要再次与 slow 相遇的话，它们之间的距离为 N ，如下图所示：

此时我们很容易推算出来 fast 走过的路程为：L + ( x + 1 ) * C - N

而 fast 要追上 slow 还有 N 的路程需要走

而因为 fast 与 slow 速率比为 2 ：1，故当slow进入环时，fast 与 slow 同时在环内进行移动操作，每一次位移都会让它们之间的距离缩小 1，及需要追赶的路程从 N 变为 N - 1，依次逐步，直到为0。
即N - 2
N - 3
N - 4
……
2
1
0

当 fast 追上 slow 时,
slow 走过的路程为：L + N
fast 走过的路程为 L + ( X + 1 ) * C + N = 2L + 2N
故此时 slow 距离入环点还有 C - N 的距离。
如下图所示：
在这里插入图片描述
而在上面分析中通过 fast 走过的路程 L + ( X + 1 ) * C + N = 2L + 2N，可以推算出 L = ( X + 1) * C - N，即 L = X * C + C - N，故当 point 从头节点出发，走过 L 后到达入环点，此时 slow 又从它与 fast 相遇的位置走了 X 圈环后，又走了 C - N的距离，即此时 slow 也刚好到达入环点，也就是此时 point 与 slow 相遇，此时的 point 就为入环点。

三. 代码展示

代码展示如下：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode, * pListNode;
struct ListNode* detectCycle(struct ListNode* head)
{pListNode slow = head;pListNode fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;if (fast == slow){pListNode point = head;while (point != slow){point = point->next;slow = slow->next;}return point;}}return NULL;
}