一、什么是环形链表
环形链表是一种特殊类型的链表数据结构，其最后一个节点的"下一个"指针指向链表中的某个节点，形成一个闭环。换句话说，链表的最后一个节点连接到了链表中的某个中间节点，而不是通常情况下连接到空指针(null)。如图：
由于链表最后一个节点的下一个指针没有指向NULL，而是指向前面的某一个节点，所以我们不能再用 “current->next==NULL” 作为判断条件来遍历链表（这样会造成死循环），通常使用快慢指针来控制条件，下面的两个题目都是要借助快慢指针来实现。
二、判断是否有环
题目给我们一个链表让我们判断链表中是否存在环，那么我们是否可以直接遍历一遍呢？没有环就会遍历到NULL，那我们就可以直接返回FALSE，否则如果存在环的话就会走到重复的节点，那就返回TRUE不就好啦？
一开始肯定会有同学会这样想，但是实际上，如果不存在环的话我们很容易判断，可如果有环的话我们又怎么判断这个节点是已经走过的节点呢？如果要把地址储存起来又很麻烦。
我们需要换一种解题方式，这里我们只用一个指针时肯定无法判断一个节点是否已经走过的，那么我们是否可以再增加一个指针，两个指针走的速度不同，走的快的指针先入环，走的慢的指针后入环。
之后这个题目就变成了追及与相遇问题，两个指针都在环中走，走的快的肯定可以追上走的慢的，当它们相遇时就说明存在环，否则当走的快的遇到NULL时，就说明不存在环。
代码示例如下：
struct ListNode* fast, *slow; fast = slow = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; if(slow == fast) return true; } return false;
分析：
1. 为什么循环的结束条件是fast或者fast->next指向NULL？
- 当一个链表中有环时，fast和fast->next永远不会指向NULL。
- 当一个链表中没有环时，fast一定会移动到链表的结尾；又因为fast一次移动两个节点，所以有三种情况：
- fast移动两次后，刚好指向NULL，结束循环。
- fast移动一次后就已经指向NULL，此时再进行移动，就会出现对NULL的解引用。
- 链表本身就是空链表，fast->next会对NULL解引用。
2. 为什么要求快指针fast一次移动两个节点，慢指针slow一次移动一个节点？
- 快指针fast一次移动两个节点，慢指针slow一次移动一个节点，两者一定会相遇吗？
移动的过程中有一下三种状态：
1）快指针fast和慢指针slow都没有进入环的入口点
2）快指针fast进入环的入口点（或已在环内）、慢指针slow没有进入环的入口点
3）快指针fast和慢指针slow都在环内
如果快指针fast和慢指针slow相遇，一定是在环内相遇，所以我们主要分析一下第三种状态。
此时fast和slow的距离设为N，当fast和slow每次移动时，速度差为1，两者的距离就会变成N-1（fast向前移动两个，slow向前移动一个，所以距离就近一个），移动一次两者的距离就-1，直到N会被减小到零，两者就相遇了。
快指针fast一次移动两个节点，慢指针slow一次移动一个节点时，两者一定会相遇。
- fast一次不能移动三个/四个节点吗？
可以用同样的分析方法，来分析一下fast一次移动三个/四个节点的情况。
1）fast一次移动三个节点的情况：
此时fast和slow的距离设为N，当fast和slow每次移动时，两者的距离就会减小2。
不难发现，如果是每移动一次距离减2的话，可能会出现N不会减到0的情况，所以这里有以下两种情况：
- N为2的倍数时，N可以被减到零，快慢指针会相遇；（在未减到0之前，fast一直在slow的后面，fast追slow）
- N不为2的倍数时（奇数）， N不会被减到0，N最后一次会被减到1，此时fast再向前移动2个节点、slow向前移动1个节点时，fast会领先slow一圈，这时fast会跑到slow的前面一个节点，此后可能会重复上述过程，也就是说fast不会相遇。
所以fast一次移动三个节点，fast和slow不一定会相遇，它有两个影响点：
- 与环的长度
（C-1）是否是2的倍数
- 环入口点之前节点的个数有关
N是否是2的倍数-->在slow还没有到达环入口点前，fast会在环内一直循环，环入口点之前节点的个数不同，当slow到达环入口点时，fast的与slow的相对位置会不同，这样N就不同
2）fast一次移动四个节点的情况
移动四个节点的分析方法与三个的相同
- N为3的倍数时，N可以被减到零，快慢指针会相遇；（在未减到0之前，fast一直在slow的后面，fast追slow）
- N不为3的倍数时，N不会被减到0，N最后一次会被减到1或2，此时fast再向前移动3个节点、slow向前移动1个节点时，fast会领先slow一圈，这时fast会跑到slow的前面一个或两个节点，此后可能会重复上述过程，也就是说fast不会相遇。
三、寻找环的入口
方法：
- 用之前的快慢指针方式找到相遇点
- 将一个指针指向开头
- 将指向开头的指针和指向相遇点的指针以相同的速度向后移动
- 再次相交的结果就是相遇点
代码示例如下：
struct ListNode *detectCycle(struct ListNode *head) { struct ListNode* fast, *slow; fast = slow = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; if(slow == fast) { struct ListNode* meet = slow; struct ListNode* cur = head; while(meet != cur) { meet = meet->next; cur = cur->next; } return meet; } } return NULL; }
分析：
（设环的长度为C）当慢指针slow到达相遇点时，slow走过的距离设为L+X，则快指针fast走过的距离为L+X+n*C （n是slow为到达环入口点时，fast所走过环的圈数， n大于等于1）
1. slow走过的距离为什么是 L+X， 而不是L+X+圈数（即slow不会走环的一圈+X）？
最坏的情况是，如图
我们知道，如果有相同的起点，相同的时间，fast的速度是slow速度的二倍，所以fast走过的距离是slow的二倍，所以当slow回到起点时，fast刚好第二次回到起点，此时两者相遇，而slow也只是走了一圈。
由于走过前面 L 长度的节点后，fast和slow之间一定有距离，所以当slow第一次到达环的入口点时，fast可能不在环的入口点。如果slow再走完一圈，fast会走两圈，速度差为1，在此期间肯定会相遇。
2. fast走过的距离为什么是 L+X+n*C，并且n大于等于1？
这里我解释一下 “n*C，并且N大于等于1”，由于slow一次移动一个节点，fast一次移动两个节点，相同的时间下，fast的速度大于slow的速度，两者走过的距离肯定不相同，所以第一圈内，slow和fast不会相遇，只有当fast超过slow一圈或几圈后，两者才能相遇。
3. 为什么头结点到入口的距离等于相遇点到入口的距离
由数学推导可知：
因为fast走过的距离是slow走过距离的二倍，所以有 L+X+n*C = 2*（L+X）
进一步化简得，n*C = L+X，即（n-1）*C + C = L + X
又因为fast在环上转了（n-1）圈，但是fast与slow的相对位置不变，所以得到下式：
C = L + X
所以：
L= C - X = N （N是相遇点与环的入口点的距离）
其他方法：
当然，寻找环的入口点还可以用另一种方法：
让快慢指针相遇点与下一个节点断开，然后将问题转化为两个链表的相交，环的入口点其实就是两个链表的相交点。
代码示例如下：
struct ListNode* cur1 = headA; struct ListNode* cur2 = headB; int la = 1,lb = 1; if(!headA || !headB) return NULL; while(cur1->next) { cur1 = cur1->next; la++; } while(cur2->next) { cur2 = cur2->next; lb++; } if(cur1 != cur2) return NULL; struct ListNode *LongList = headA; struct ListNode *ShortList = headB; if(la < lb) { LongList = headB; ShortList = headA; } else { LongList = headA; ShortList = headB; } int n = la > lb? la-lb:lb-la; while(n--) LongList = LongList->next; while(LongList != ShortList) { LongList = LongList->next; ShortList = ShortList->next; } return LongList; }
