判断单链表是否有环、求环长和环入口最优算法
判断单链表是否有环是一个十分经典的算法问题，许多考试或者面试都有很大的几率出现。如果事先对此没有一定的理解，临场发挥可能就比较困难了。
判断链表是否有环
- 首先定义两个指针 slow 和 fast，初始都指向链表头指针 head；
- 然后，slow 每走一步（每次移动一个节点），fast 走两步（移动两个节点）；
- 如果 fast 遇到了 NULL，则链表不存在环；
- 如果 slow==fast，则链表存在环；
判断单链表是否有环、求环长和环入口最优算法
为什么 slow==fast 就一定会存在环呢？
因为，如果存在环，fast 和 slow 肯定会先后进入环；
当 slow 刚好进入环时，fast 肯定已经在环内的某一个位置了；
而又因 fast 走的速度是 slow 的两倍，所以在 slow 在环内遍历一遍的过程中，fast 指针必然会与 slow 相遇。
其实两个指针就像是两个人在田径场上跑步，一个人的速度是另一个人速度的两倍。无论两个人的起点在何处，慢的人跑完一圈，快的人必然跑完两圈，所以他们必然相遇过。
复杂度分析
设链表长度为 n，显然时间复杂度为 O（n）；
空复杂度为 O（1）。
求环的长度
上面已经可以判断出是否有环了，如果有环，那么环的长度又是多少呢？该怎么求？
这就很简单了，前面已经将环判断出来了，所找到的 slow 和 fast 相遇点必然是在环内的，记录该节点；
所以此时只需用一个指针 p 继续一步步遍历链表，并计数，直到指针 p 重新指向上面的相遇节点，此时计数的值就为环长了。
复杂度分析
设链表长度为 n，环长为 r 。
如果是在知道一个环内节点的情况下，那么时间复杂度为 O（r），空间复杂度为 O（1）；
如果是在不知道是否有环的情况下，那么时间复杂度为 O（n+r），空间复杂度为 O（1）。
求环的入口
前面已经判断出是否有环了，并求出了环的长度，此时求环的入口也变得很简单了。
- 定义两个指针 p 和 q，初始指向链表头指针 Head；
- q 首先移动 r 个节点（r 为环的节点数），p 不动；
- 然后 p 和 q 一起每次移动一个节点；
- 直到 p==q，此时 p 和 q 指向的就是环的入口了；
这个应该很容易理解吧，q 比 p 先走了一个环的长度，所以当 p 刚好走到环的入口时，q 就刚刚好遍历了环一遍。
复杂度分析
设链表长度为 n，环长为 r 。
如果是在知道一个环长度的情况下，那么时间复杂度为 O（n），空间复杂度为 O（1）；
如果是在不知道环长度的情况下，那么时间复杂度为 O（n+r+n）= O（n+r），空间复杂度为 O（1）。
求链表的长度
链表长度 = 头结点到环入口节点的长度 + 环长度
所以此时，只需用一个指针从头遍历链表节点并计数，求出头结点到环入口节点的长度即可。
