先说一个错误思路，既然有环，那我遍历链表最终就会绕回来，同一个结点就会被访问多次，那我就标记头结点，如果他被访问两次那么就证明有环。

但你怎么直到头结点就在环中呢？以图中给的示意图为例，头结点不可能被访问两次，但他依然是一个环形链表。这样不仅不能得到正确结果，循环也无法跳出来（找不到NULL）

另一种错误思路：既然头结点不行，那我就找尾结点呗，你看上面的示意图尾结点就在环中呀。

看起来有道理，但是你怎么找尾呢？遍历链表，找若结next是NULL的结点吗？这是环形链表，哪来的尾呀？只不过图中将-4摆在了最后，按照我们平常的习惯自然就认为他是尾结点，事实上环形链表是没有尾的。

正确思路如下：

定义slow和fast两个指针，slow一次走一步，fast一次走两步。如果有环的话，fast肯定会 先进入环中，在里面绕圈，随后slow也会进入环中。当slow进入环中后，fast和slow相差一定的距离（当然也有可能二者直接相遇，这样更好不过了）。由于fast每次都比slow多走一步，故fast最终肯定能追上slow和它相遇。 这是有环的情况，如果没有环，fast直接一马当先走完整个链表。

代码如下

这道题明显就是上一题的plus版，不经要判断是否有环，还要找出环的入口。 如何判断有环的方法就不赘述了，下面讲在有环的基础上如何找出环的入口：

先不加证明的给出一个结论：如果链表有环，那么fast和slow一定会在环中的某个点相遇，我们令一个指针meet从相遇点开始，另一个指针head从头开始，二者每次都走一步，最终当head进入环时，meet刚好和他相遇。换句话说，meet和head的相遇点刚好就是环的入口

代码如下：

证明过程如下：

上面的方法不容易想到，本本题还有另一种解法：

slow和发生相遇之后，将相遇点后面的结点置为NULL，这样一个链表就分成了两个链表，然后就转化为了链表相交问题，两个链表的第一个公共结点就是环的入口。（链表相交问题）

代码如下：

这里的关键在于如何处理拷贝结点的random域，怎么找到原链表中一个结点的random指向的结点 对应的拷贝结点呢？可以通过random结点在原链表中的位置来找，拿题目中的示意图举例，10的random结点是11，是第二个结点，那么拷贝的链表中的第二个结点即为所求。这种方法容易想到，但是复杂度是O(n^2)，不是最优解（当然能做出来就不错了）。

另一个思路就是，将拷贝的结点插入到原结点之后，那么拷贝结点的random就是原结点的random的next，如下图所示，最终再将拷贝结点与原结点分开形成一个链表，新链表即为所求。

代码实现；