环形链表（详解）
第一题：
题目：
题目链接
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
思路：
首先我们创建一个快慢指针，让其在链表内不断走，如果链表是带环的，那么快指针迟早会追上慢指针，追上了那就是带环链表。
但是注意了在这里
我们的快慢指针之间的速度差距一定得是——fast = 2slow，即是慢指针走1步，快指针走两步。
为什么呢？
我们假设slow指针进入环时离fast指针的距离是X。
- 当X == 0的时候，slow一进环就碰到fast了，说明第一个节点到环的长度和环内的长度是一样的。
- 如果slow走到环的长度是，环内的一半长度，这个时候，slow进环的时候，fast刚好在环中间。如图所示
- 也就是说，当slow慢指针入环之后，fast和slow每走一次，他们之间的距离X都会-1.如图所示
其实就证明了，slow入环之后，和fast的距离是X，slow再走X次，fast就能追上slow指针。
那为什么说fast只能是slow的两倍速率呢？
因为如果我们的fast走其他步 比如3步 4步，就有可能会不相遇！
如图所示，如果X是奇数，比如是1，那么一次走三步就会直接跳过去，那么此时的X就会重置为环的长度-1，如果这个新的X也是奇数，那么就会死循环！
fast走其他步也是同样的道理，这里就不在例举。
因此其他步总有一些特殊的情况无法处理，无法相遇。
但是如果fast每次走两步，每次的距离减少1 那就一定会相遇。
因此这里只能让fast = 2slow。
慢指针在环内是走不到一圈的，严格来说，最差的情况是slow在入环第一个节点，fast在入环第二个节点，这个时候慢指针走接近2/3圈就会被追上。
代码实现：
struct ListNode
{
int val;
struct ListNode* next;
};
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode* head)
{
// 创建快慢指针
ListNode* slow, * fast;
slow = fast = head;
// 快慢指针都在环里面一直走下去，快指针迟早能追上慢的指针
while (fast && fast->next) // 我们不知道传进来的链表是不是带环的因此，fast和fast->next 都不能为NULL
{
slow = slow->next;
fast = fast->next->next; // 注意了这里的快指针只能是 fast = 2slow
// 如果快指针追上慢指针那就是带环
if (fast == slow)
return true;
}
// 走到这里说明 不带环
return false;
}
第二题：(难度：中等)
题目：
题目链接
如果链表中有某个节点，可以通过连续跟踪 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
解释：链表中没有环。
思路：
思路1：（理解容易，写起来较麻烦）
- 创建快慢指针，如果有环就相遇，无环无法相遇
- 首先让fast和slow相遇，找到这个相遇的节点。
- 然后把相遇的节点断开
- 然后相遇点和到相遇点的上一个节点是一个链表，一开始的链表头到断点也是一个链表。
- 这个时候我们把问题转化成了两个链表的相交问题，找到交点，这个交点就是题目要找的入环的第一个节点！
代码实现：
struct ListNode
{
int val;
struct ListNode* next;
};
typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head)
{
// 排除空链表的情况
if(head == NULL)
return NULL;
// 创建快慢指针
ListNode* slow, *fast;
slow = fast = head;
// 让快慢指针遍历链表，看看带环
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
// 判断是否有相遇点
if(slow == fast)
break;
}
// 排除不带环的情况
if(slow != fast)
return NULL;
// 让相遇点断开
ListNode* next = slow->next; // 让next存储相遇点的下一个节点
slow->next = NULL; // 断开相遇点
// 这个时候next 和 head 分别为两条链表
// 这个时候我们就找这两个链表的相交点就好了，交点就是入环第一个节点
// 要想找到交点首先要求两个链表的长度
ListNode* curhead = head;
ListNode* curnext = next;
int lenhead = 0;
int lennext = 0;
// 遍历head链表，统计长度
while(curhead)
{
lenhead++;
curhead = curhead->next;
}
// 统计next链表长度
while(curnext)
{
lennext++;
curnext = curnext->next;
}
// 默认head为起始点的为长链表 next为起始点的为短链表
ListNode* longlist = head;
ListNode* shortlist = next;
// 判断两个链表的长度是否和我们默认的情况相同
if(lenhead < lennext)
{
// 不同就改过来
longlist = next;
shortlist = head;
}
// 计算两个链表的长度差
int gap = abs(lenhead - lennext);
// 让长链表走两个链表的长度差
while(gap--)
{
longlist = longlist->next;
}
// 这个时候长短链表的长度相同了
while(longlist)
{
// 这个时候要判断next指向的是否是入环的第一个节点，因为快慢指针的相遇点可能是入环的最后一个节点
// 因此要先判断是否为交点
if(longlist == shortlist)
return longlist;
// 让两个链表都向后走
longlist = longlist->next;
shortlist = shortlist->next;
}
// 如果走到这里就说明有情况没有排除
// 比如链表只有一个节点且不带环
return NULL;
}
思路2：（理解较难，写起来比较容易）
注意 思路2一定要知道推论是怎么推出来的，要理解透彻代码是怎么来的！
-
首先找通过快慢指针找到相遇点。
-
我们假设第一个节点到入环的第一个节点的距离叫做L，把slow指针入环后走的距离叫X，环的长度是C。如图所示
-
-
那么慢指针走的距离就是：L + X (慢指针在环内一定走不过一圈)
-
快指针走的距离就是： L + N * C + X (N代表走的环的圈数)
如果L短C大 也就是环的长度大 那么N就小，就是快指针绕环走的圈数少
如果L长C小，也就是环的长度小，N就大，就是快指针要绕环走很多圈，慢指针才能入环。
如图所示，L长C小的情况，N会比较大
- 我们又知道 2slow = fast 也就是2(L + X) = L + N*C + X
- 推论得知 L = N*C - X. 也就是第一个节点到入环的第一个节点的距离L = 快指针在环内走的长度N * C 再减去一个慢指针入环的距离 X
也可以理解成 L = （N-1） C + C - X*
也就是fast走了（N-1）* C 的距离后再走了一个 C - X的距离就是L的长度
- 也就是说从相遇点有一个指针，和链表的起始点开始一起走，两个指针相遇的节点就是我们要找的入环的第一个节点
代码实现：
struct ListNode
{
int val;
struct ListNode* next;
};
typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head)
{
// 首先创建快慢指针
ListNode* slow, *fast;
slow = fast = head;
// 通过快慢指针判断是否带环,并且让slow和fast相遇时就退出
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
// 如果相遇就退出
if(slow == fast)
break;
}
// 走到这里有可能时slow == fast 也有可能链表不是带环链表
// 传入空链表的情况也要排除
// 如果链表只有一个节点且不自身成环的情况要排除
if(fast == NULL || fast->next == NULL) // 排除不是带环链表的情况
return NULL;
// 让相遇点和链表起始点同时开始走，当两个指针相遇的时候，这个节点就是入环的第一个节点
// 注意！这里是一个推论，切记不可不知道推论怎么来的！
// 推论详解 看自己的笔记或者博客。博客地址：
ListNode* meet = slow;
while(meet != head)
{
meet = meet->next;
head = head->next;
}
// 走到这里meet和head指向的节点就是入环的第一个节点
return meet;
}
