LeetCode 142题解｜环形链表II的快慢指针法（含数学证明）

题目如下：

解题过程如下：

思路：快慢指针在环里一定会相遇，相遇结点到入环起始结点的距离 == 链表头结点到入环起始结点的距离（距离看从左往右的方向，也就是单链表的方向），从链表头结点和相遇结点遍历，只要结点一样，那么这个结点就是入环起始结点。

示例1、示例2为例，

示例1：相遇结点到入环起始结点的距离1 == 链表头结点到入环起始结点的距离1

示例2：相遇结点到入环起始结点的距离0 == 链表头结点到入环起始结点的距离0

完整代码如下：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {//快慢指针ListNode* slow = head;ListNode* fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;//快慢指针相遇if (slow == fast){//链表头结点和相遇结点开始往后遍历，结点一样，这个结点就是入环起始结点ListNode* pcur = head;while (slow != pcur){slow = slow->next;pcur = pcur->next;}return slow;}}//fast == NULL 或 fast->next == NULL，跳出循环，说明没有环return NULL;
}

试着证明：

为什么在带环链表中，链表的头结点和快慢指针相遇结点到入环起始结点的距离相等？

假设：链表的头结点到入环起始结点的距离是L，环的周长是R，若slow刚刚入环时fast已经在环里绕了n圈了（n至少为1，因为fast先进环中到M点，后又和slow在M点相遇），入环起始结点到相遇结点之间的距离是X。

慢指针进环后，快指针肯定会在慢指针走一圈之内追上慢指针。因为在快慢指针都进环之后，快慢指针之间的距离最多就是一个环的周长，快指针每追击1次，二者之间的距离就会缩小1步，所以，在慢指针移动一圈之前，快指针一定会追上慢指针。

若已经相遇，快慢指针走过的路程：
慢指针 = L + X
快指针 = L + X + nR

由于快慢指针走过的路程之间的关系2 * 慢指针 = 快指针，得出L = nR - X = (n - 1)R + R - X，式子L = (n - 1)R + R - X（n为1，2，3，4，……，n的大小取决于环的大小，环越大n越小）中，(n - 1)R表示绕(n - 1)圈，取极端情况，n = 1时，式子最终可以看成L = R - X，即slow指针从链表起始位置开始向后遍历，fast指针在相遇点开始环绕，最终一定会在入环起始结点相遇；也就是说，在带环链表中，链表的头结点和快慢指针相遇结点到入环起始结点的距离相等。