如何检测链表中存在的环
链表有环的定义是，链表的尾节点指向了链接中间的某个节点。比如下图，如果单链表有环，则在遍历时，在通过结点J之后，会重新回到结点D。
看了上面的定义之后，如何判断一个单链表是否有环呢？
思路一：快慢指针
这个可以用昨天提到的“快慢指针”来解决吧？
设两个工作指针，一个快一个慢，如果有环的话，它们会必然在某点相遇。
算法的思想是设定两个指针p, q，其中p每次向前移动一步，q每次向前移动两步。那么如果单链表存在环，则p和q相遇；否则q将首先遇到null。
思路二：节点路径计算
设两个工作指针p、q，p总是向前走，但q每次都从头开始走，对于每个节点，看p走的步数是否和q一样。比如p从A走到D，用了4步，而q则用了14步。因而步数不等，出现矛盾，存在环。
以上面图片的环来说。p 总是向前走，而 q 每次都从头开始走，它们都从节点A出发。
第 1 次，p 走到 B 点，这时 p 走了 1 步。此时 q 从头开始走，走到 B 点也用了 1 步。没有问题。
第 2 次，p 走到 C 点，这时 p 走了 2 步。此时 q 从头开始走，走到 C 点也用了 1 步。没有问题。
……
第 12 次，p 走到 J 点，这时 p 走了 12 步。此时 q 从头开始走，走到 J 点也用了 12 步。没有问题。
第 13 次，p 走到 D 点， 这时 p 走了 14 步。此时 q 从头开始走，走到 D 点只用了 3 步。p 和 q 走到相同个位置上的步数不相等，说明链表存在环。
如果一直到 p == null 的时候还未出现步数不相等的情况，那么就说明不存在链表环。
思路三：标记法
可以遍历这个链表，遍历过的节点标记为Done，如果当目前准备遍历的节点为Done的时候，那么存在环，否则准备检测的节点为Null时，遍历完成，不存在环。
思路四：哈希表法
每个节点是只读的，不可以做标记呢？那可以另外开辟一个哈希表，每次遍历完一个节点后，判断这个节点在哈希表中是否存在，如果不存在则保存进去。如果存在，那么就说明存在环。要是取到Null还没有重复，那么就是不存在了。这个哈希表可以在 Java 语言中可以用 HashMap 实现。
那如何检测链表中是存在循环呢？