题目要求

环形链表1
问题1：
给你一个链表的头节点 head ，判断链表中是否有环。

环形链表2
给定一个链表，不仅需要判断链表中是否有环，，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
问题2在问题1的基础上，首先我们先来解决问题1.

题目1分析-求是否包含环

龟兔赛跑算法(Floyd’s Tortoise and Hare/Circle Detection)用于判断链表是否有环。具体的思路如下：
给定两个指针，一个快指针，一个慢指针，快指针一次走两步，慢指针一次走一步，在链表不存在环的情况下，快指针会达到最后的空结点，两者不会相遇。

而当链表中存在环的时候，快指针会提前进入环，而后在环内的某个结点处会和慢指针重合。

那么为什么快指针和慢指针一定会重合呢？
我们可以思考这样的一个情境，A和B同时在操场中跑步，其中A的速度是B的2倍，那么一开始A会超过B，之后：因为A的速度大于B的速度，那么在某一个时刻：A一定会和B再度相遇，再度超过B。但是要如何用数学公式证明呢，具体的证明可以参考这篇文章，写的很详细：证明过程

我是这么理解的：
如下所示：每次指针向前移动之后，快指针和慢指针之间的距离就会增加1。进入环中，一旦快指针超过慢指针之后，快指针在追赶慢指针的过程中，它们之间的距离每次都会缩短1个单位。而因为慢指针每次是向前移动1个单位的，因此，快指针在向前移动的过程中，一定会和慢指针在某个时间点重合。

所以问题就变得简单起来了：只要在两个指针向后移动的过程中，每次判断两者所指向的结点地址是否相同就可以。

代码如下：

class Solution {
public:bool hasCycle(ListNode *head) {ListNode* fast=head;ListNode* slow=head;while(fast!=nullptr && fast->next!=nullptr){slow=slow->next;fast=fast->next->next;if(slow ==fast)return true;}return false;}
};

题目2分析-求入环结点

那么要如何找到入环的结点呢？这里涉及到简单的数学推导，主要参考的这篇文章：如何确定环的起点

假设：从头结点到入环结点之间的距离为m,从入环结点到两个指针重合的点之间的距离为n。环的长度为s，慢指针的步数为i步，快指针的步数为2i步。
(1).当快指针和慢指针相遇的时候有以下两个公式:
$$2i=m+n+a\ast s$$ $$i=m+n+b\ast s$$
a和b分别代表的是快指针跑的圈数和慢指针跑的圈数。
两式相减可以得到：
i=(b-a)*s
经过简单的推导可以发现：两者相遇的时候：慢指针所走的步数是等于环长度的整数倍。
快指针和慢指针相遇的时候：多走的部分恰好是绿色笔划出来的部分，即是环的长度的整数倍

(2)此时，让指针从链表的头部，一直向前走到环的入口结点处并统计步数k，那么步数k=m+i.这里的i是环的长度的整数倍，因为不管绕几圈，都会来到入口结点处。

(3)此时慢指针已经走了i步了(两者相遇的时候)，那么只需要慢指针向前走m步，就可以走到入口结点处。那么问题就转换为如何求m的取值。

**此时令快指针指向链表的头结点处，快指针每次走1步。**此时快指针和慢指针同时走m步后，两个指针会重合，故该指针指向的结点即为入口结点处。
代码如下:

class Solution {
public:ListNode *detectCycle(ListNode *head) {//快慢指针的方法ListNode* fast=head;ListNode* slow=head;//    fast->next为空的话，下面的fast->next将有可能出现程序崩溃的现象。while(fast!=nullptr && fast->next!=nullptr){fast=fast->next->next;slow=slow->next;//    代表有环if(fast ==slow){//    fast指向头结点,fast向前移动m个点之后就会和slow在环的起点处重逢。fast=head;while(fast!=slow){slow=slow->next;fast=fast->next;}//两者相等的时候：代表走到入环处return fast;}}return nullptr;}
};

拓展分析：如何求环的长度?

思路也很简单：快指针和慢指针相遇之后，快指针保持不动，慢指针向前移动。直到两者再次相等的时候，就可以计算出环的长度。

int cyclelength(ListNode* head)
{ListNode* fast=head;ListNode* slow=head;while(fast!=nullptr && fast->next!=nullptr){fast=fast->next->next;slow=slow->next;//代表有环if(fast ==slow){//初始化令i=1,即代表相交处的结点。int i=1;do{slow=slow->next;i++;}while(slow!=fast)return i;}}return 0;}