主要内容 #
- 问题描述
- 求解思路
- 参考代码
1. 问题描述 #
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
说明：不允许修改给定的链表。
你是否可以不用额外空间解决此题？
例子1:
输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。
例子2:
输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点 解释：链表中有一个环，其尾部连接到第一个节点。
例子3:
输入：head = [1], pos = -1 输出：返回 null 解释：链表中没有环。
2. 求解思路 #
判断链表中是否有环时我们使用快慢指针发来判断：
快慢双指针法主要步骤为：定义两个指针，一个 slow 指针，一次走一步；另一个 fast 指针，一次走两步。如果可以在某一个点满足 slow=fast，那么就说明存在环，否则 fast 指针必然先到到终点。
fast 指针在任何时候走的距离一定是 slow 指针的 2 倍，这个结论我想大家都没什么疑问，知道了这个结论之后，我们再来看一下下面这幅图：
上图中以节点为划分，有三段链表，a，b，c 分别表示三段的距离，我们假设当快慢指针相遇的时候，快指针已经在环中走了 n 圈，那么就可以得到快指针走过的距离为：a+n*(b+c)+b，而慢指针走过的距离为 a+b，根据快指针走的路程一定是慢指针的两倍，可以得到如下等式：
a+n*(b+c)+b = 2*(a+b)，最终经过转换，得到 a=(n-1)*(b+c) + c。
到这里可能有人会有疑问，快慢指针相遇的时候，为什么慢指针一定没有走完一圈呢？如果慢指针也走了 m 圈，那么慢指针走过的距离就是 a+m*(b+c)+b 了，但是这其实是不可能的。
为什么快慢指针相遇时慢指针没有走完一圈
我们假设这个环的长度为 x，那么当 slow 指针走完一圈时，需要走 x 步，而当 slow 指针走完 x 步，fast 指针已经走了 2x 步了，也就是走了两圈了，那么他们一定在某一个点相遇过了（因为他们不可能错过相遇点），所以当快慢指针第一次相遇时，慢指针是不可能走完一圈的。
利用第三个指针找到环的位置
继续回到上面的等式：a=(n-1)*(b+c) + c，然后我们可以发现，其实 b+c 正好等于环的长度，也就是说：从链表头部到入环的距离（a）恰好等于从相遇点到入环点的距离（c）再加上 n-1 圈个环的长度。
这时候就有个有趣的现象了，如果 slow 和 fast 相遇了，那么这时候我们再定义一个指针指向链表起点，一次走一步，slow 指针也同步继续往后走，那么这两个指针就一定会在链表的入口位置相遇。
3. 参考代码 #
/**
* 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) {
ListNode* fast = head;
ListNode* slow = head;
while(fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
// 快慢指针相遇，此时从head 和 相遇点，同时查找直至相遇
if (slow == fast) {
ListNode* index1 = fast;
ListNode* index2 = head;
while (index1 != index2) {
index1 = index1->next;
index2 = index2->next;
}
return index2; // 返回环的入口
}
}
return NULL;
}
};
