难度中等1940
给定一个链表的头节点 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 <= 105pos的值为-1或者链表中的一个有效索引
**进阶：**你是否可以使用 O(1) 空间解决此题？
解题思路：快慢指针
1、判断是否存在环 141. 环形链表
判断是否存在环，那么我们可以用快慢指针，快指针走两步，慢指针走一步，那么肯定快指针要先入环，而等到慢指针入环的时候，此时快指针可能在慢指针后面，也可能在慢指针前面，这个时候就变成了追逐的情形了。
而我们控制快指针走两步，慢指针走一步，如果有环的话，那么它们在环中每次都会以相差一步的长度在不断缩小距离，因为慢指针走一步，快指针走两步！
所以这样子的话就能保证在环中两个指针相遇，相遇说明就是有环，而不相遇，且快指针已经为空，那么说明不存在环！
下面给出两个常见的面试问题：
① 为什么slow走一步，fast走两步，它们一定会在环里面相遇，会不会永远追不上？请证明！
② slow走一步，fast走三步呢？fast走四步呢？走n步呢？行不行呢，请证明？
2、若有环如何找到入口？
这里有两种方法，我们一一介绍：
① 第一种方法（思路较难，实现简单）：
至于为什么慢指针只走了不到一圈呢？？？仔细想想，假设快指针和慢指针的距离是 N，那么这个 N 肯定是不会比环的长度大的，也就是说 N <= C，那么每次距离变小一步也就是 N-1，那么就能推导出不到一圈的距离，慢指针就被赶上了！
而快指针走了多少圈，这是取决于这个圈的大小和位置的，无法确定！
/**
* 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 != nullptr && fast->next != nullptr)
{
fast = fast->next->next;
slow = slow->next;
if(fast == slow)
{
// 与头节点一起走，直到走到节点相同则为环入口
ListNode* meet = head;
while(slow != meet)
{
meet = meet->next;
slow = slow->next;
}
return meet;
}
}
return nullptr; // 若遇到空则说明无环
}
};② 第二种方法（思路简单，实现较复杂）：
先利用快指针和慢指针找到相遇点，然后将该点置空，然后从下一个节点开始走，同时头节点位置也开始走，这样子的话就转化为了 链表求相交点的问题！
/**
* 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 != nullptr && fast->next != nullptr)
{
fast = fast->next->next;
slow = slow->next;
if(fast == slow)
break;
}
// 判断是否有环，空则无环
if(fast == nullptr)
return fast;
ListNode* meet = fast->next;
fast->next = nullptr; // 这是为了后面判断相交链表的时候链表的尾部必须指向空
// 求两条链的节点个数
int numMeet = 0, numHead = 0;
ListNode* cur1 = meet, *cur2 = head;
while(cur1)
{
cur1 = cur1->next;
numMeet++;
}
while(cur2)
{
cur2 = cur2->next;
numHead++;
}
// 将长的那条链表移动差值位
while(numMeet != numHead)
{
if(numMeet > numHead)
{
numMeet--;
meet = meet->next;
}
else
{
numHead--;
head = head->next;
}
}
// 最后判断是否有相交节点
while(meet != head)
{
meet = meet->next;
head = head->next;
}
return meet;
}
};