题目链接：leetcode142

题面

题目大意

给你一个链表可能有环，如果有环输出环的入口节点，否则输出 NULL

解题思路

双指针

首先快慢指针进行找环，之后根据滑动窗口寻找入口。

我们可以大致证明一下：

假设慢指针走的长度为 $la$ ，快指针走的长度为 $lb$ ，整个链表的节点个数为 $s$。那么，整个环的长度可以等于 $lb-la$，非环部分的长度为 $s-(lb-la)$ ，又因为快指针的长度为慢指针的两倍，即 $lb=2la$ ，所以环的长度也等于 $la$ ，非环部分的长度也等于 $s-la$ 。于是，找环最终的位置到链表环的最右侧的长度为 $s-la$ ，恰好走完它回到环的入口时，定义的窗口的左指针也走了 $s-la$ 也到达环的入口，此时算法结束。证毕。

实现代码

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {if (head == NULL) return NULL;ListNode *p, *q;p = q = head;        while (q && q->next) {p = p->next;q = q->next->next;if (q == p) break;}if (!q || !q->next) return NULL;p = head;while (q != p) {q = q->next;p = p->next;}return q;}
};