/*
* **************************************************************************
* ******************** ********************
* ******************** COPYRIGHT INFORMATION ********************
* ******************** ********************
* **************************************************************************
* *
* _oo8oo_ *
* o8888888o *
* 88" . "88 *
* (| -_- |) *
* 0\ = /0 *
* ___/'==='\___ *
* .' \\| |// '. *
* / \\||| : |||// \ *
* / _||||| -:- |||||_ \ *
* | | \\\ - /// | | *
* | \_| ''\---/'' |_/ | *
* \ .-\__ '-' __/-. / *
* ___'. .' /--.--\ '. .'___ *
* ."" '< '.___\_<|>_/___.' >' "". *
* | | : `- \`.:`\ _ /`:.`/ -` : | | *
* \ \ `-. \_ __\ /__ _/ .-` / / *
* =====`-.____`.___ \_____/ ___.`____.-`===== *
* `=---=` *
* **************************************************************************
* ******************** ********************
* ******************** ********************
* ******************** 佛祖保佑 永远无BUG ********************
* ******************** ********************
* **************************************************************************
*/目录
正文开始
（一）环形链表I
给你一个链表的头节点
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 解释：链表中没有环。提示：
- 链表中节点的数目范围是
[0, 10000]-100000 <= Node.val <= 100000pos为-1或者链表中的一个 有效索引 。进阶：你能用
O(1)（即，常量）内存解决此问题吗？
（1）追随思路分析
通过审题，我们知道链表是不一定有环的；其次，如果链表有环，那么成环的节点个数是不确定的：（两个界限是循环链表和链表尾部成环）
当链表不成环，可以创建pcur指针从第一个节点来遍历链表
struct ListNode* pcur = head;
while(pcur)
{
pcur = pcur->next;
}
return pcur;由于单链表最后一个节点指向空，所以最后pcur会为NULL，循环会停下来。
但是当链表成环，pcur如果还用上面的这种写法，pcur是停不下来的，会导致死循环。这解决判断链表是否成环的问题后，又带来了新的问题：
进程停不下来，自然无法返回任何值！
自然也就无法返回ture或者false了。
这时，我们不妨思考一下：
有环与无环到底有什么区别？表现出来有什么不同？
无环，最简单的while（pcur）思路甚至就可以停下来；有环，意味着停不下来，停不下来，但是，在无尽的循环中，总要有一些变化吧！这个变化，就是对速度的积分——路程！
（2）快慢指针解围
快慢指针是一种常用的算法技巧，通常用于解决链表相关的问题。快慢指针指的是在遍历链表时，使用两个指针分别以不同的速度移动，从而达到某种特定的目的。
在具体的应用中，快慢指针有不同的用法和含义。下面介绍几种常见的应用场景：
判断链表是否有环：使用快慢指针遍历链表，如果快指针和慢指针最终相遇，则说明链表中存在环。
查找链表的中间节点：使用快慢指针遍历链表，快指针每次移动两步，慢指针每次移动一步，当快指针到达链表末尾时，慢指针指向的节点即为链表的中间节点。
判断链表的回文性：使用快慢指针遍历链表，同时使用一个栈来保存慢指针遍历过的节点值。当快指针到达链表末尾时，慢指针指向链表中间节点。然后将慢指针继续往前遍历，同时从栈中取出节点值进行比较，如果都相等，则链表为回文。
寻找链表倒数第k个节点：使用快慢指针遍历链表，让快指针先移动k个位置，然后快慢指针同时向前移动，当快指针到达链表末尾时，慢指针指向的节点即为倒数第k个节点。
总结来说，快慢指针是一种非常简单有效的算法技巧，可以用于解决链表相关问题中的一些特定需求，如判断环、寻找中间节点、寻找倒数第k个节点等。使用快慢指针可以将时间复杂度从O(n^2)降低到O(n)，提高算法的效率。
我们让快指针一次走两步，慢指针一次走一步，当两个指针都进入环后，快指针最终会追上慢指针，这可以作为while终止的条件；
环形链表I代码实现如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode LS;
bool hasCycle(struct ListNode *head) {
LS *fast = head;
LS *slow = head;
while(fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if(fast == slow)
{
return true;
}
}
return false;
}
（二）环形链表II
给定一个链表的头节点
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, 10000]内-100000 <= Node.val <= 100000pos的值为-1或者链表中的一个有效索引进阶：你是否可以使用
O(1)空间解决此题？
（1）思路分析
与第一题相似，要求判断链表是否带环；也是第一题的深入，要求返回环的起始节点；
在思考一番无果后，我们不妨先仔细想一想这个问题：
为什么慢指针一次走一步，快指针一次走两步？这样走，慢一定会追上快吗？
如果慢指针走一步，快指针走三步呢？这样能相遇吗？
满指针走两步，快指针走三步呢？
这里先留作思考，如果你想要弄个明白，首先推荐自己分析，其次第二题的详细分析在下篇。
完~
未经作者同意禁止转载
![<span style='color:red;'>C</span><span style='color:red;'>语言</span> [<span style='color:red;'>力</span><span style='color:red;'>扣</span>]详解<span style='color:red;'>环形</span><span style='color:red;'>链</span><span style='color:red;'>表</span>和<span style='color:red;'>环形</span><span style='color:red;'>链</span><span style='color:red;'>表</span>II](https://img-blog.csdnimg.cn/direct/73b177a9347f4ac081b371f93dadf76c.png)
