单链表有关 环 的问题
说起关于单链表的环，无非以下几种常见问题 。
有时还会问道带环链表的总长度， 环长度+头节点到入环点长度就好，也就是问题2，3的结合。
如预期一样，789开始无限循环
1求单链表是否有环 。
2求单链表的入环点。
3求环的长度。
对于问题1，记得我第一次接触的时候，比较暴力，直接定义了个数组存放链表所有节点的地址。 遍历链表每读到下一个节点的时候，都要和已知结点的地址数组比较，看是否相同。这种解法的优点 仅仅是的确很好想，但时间复杂度 空间复杂度都很高。
因此就要寻找更优的解法，我起初的那个很差且很low的解法可以扔了。
新解法的突破口在哪里呢。
想想单链表涉及的很多减少复杂度的做法都是定义快慢指针。
比如打印单链表中间节点的值，链表长度未知。
大部分人一开始是先遍历下链表，确认长度，然后长度取半，再遍历到一半的位置。
其实更优的做法是，定义快慢两个指针，两者同时遍历，快指针一下往后遍历2个结点，慢指针一下往后遍历1个结点，等到快指针到链表尾巴了，慢指针也走到中间了，打印慢指针所指结点信息就ok了。
再比如打印单链表倒数第k个的值，链表长度位置。
大部分人一开始也是遍历链表确认长度，然后让 再遍历到 （长度-k）的位置打印。
更优做法是，定义快慢指针，快指针先走k个结点，然后慢指针出发，快慢指针同时往后走，快指针到末尾时，慢指针就自然到了倒数k的位置。
还有类似的问题。。。。
因此我们能发现单链表和快慢指针有着莫大的关联！！
因此新解法就从这点作为启发出发，带环链表的特点是什么？小笨猪都知道是会从 入环点开始循环。
快慢指针？循环？ 是否联想到追击相遇问题？
定义快指针每次走2个结点，慢指针走1个结点，如果链表没有环，慢指针一辈子也追不上快指针。
但是有环了就代表快指针到达目的地就会开始打转，慢指针追上快指针成为了可能。
因此判断是否有环函数非常简单。
快指针遇到NULL就代表有结尾，自然就没有环。
在快指针没遇到NULL的情况下，被慢指针追上了，就代表环的存在。
图示
红色快指针
蓝色慢指针
给了两个带环链表
绿色圈起的结点为相遇点，这个点对于后两个问题来说非常重要！！！
有人会担心一种情况，慢指针进入环区了，然后快指针再次进环，快指针增长大会再次超过慢指针，导致判断 （慢指针==快指针）被略过。其实并不会！ 从快慢指针跳跃长度来想，快指针一下跳2次，慢指针一下跳一次，出现那种情况的前提是，上一步慢指针已经和快指针相等了，然后快指针才能跳过慢指针。但是如果上一步已经相等了，我们还能进入到这一步吗？显然不能的。
该求问题2 求单链表的入环点。
还记得刚才的绿色圈起的相遇点吗
再定义一个指针从头节点触发，慢指针从相遇点出发，两个指针总会在入环点处碰面。
至于为什么这样做？它的原理是什么？那就是：记住就好了
3求环的长度。
其实和2问题有些像，那就是继问题1后，快慢指针从相遇点继续按照快指针2结点，慢指针1结点 走，快慢再次相遇时，它们走过的结点数就是环的长度。
有时还会问道带环链表的总长度， 环长度+头节点到入环点长度就好，也就是问题2，3的结合。
测试一下。创建一个带环链表，0 1 2 3 4 5 6 7 8 9 入环点选7
如预期一样，789开始无限循环
判断是否有环
获取入环点
获取环长度
结果如下
