详解：如何判断链表中是否有环？
如何判断链表中是否有环是一道非常经典的题目，下面用3种方法实现。
方法一：暴力双重循环
直接使用双重循环，没什么好讲的。
方法二：使用HashSet
在方法一的基础上进行优化降低复杂度，使用hashSet作为额外缓存，可以减少一层循环，具体思路如下: 首先创建一个以节点ID为Key的HashSet集合，用来存储曾经遍历过的节点。然后同样从头节点开始，依次遍历单链表中的每一个节点。每遍历一个新节点，都用新节点和HashSet集合中存储的节点进行比较，如果发现HashSet中存在与之相同的节点ID，则说明链表有环，如果HashSet中不存在与新节点相同的节点ID，就把这个新节点ID存入HashSet中，之后进入下一节点，继续重复刚才的操作。 使用HashSet将算法的时间复杂度降为了O（n）
方法三：利用两个指针
首先创建两个指针p1和p2（在Java里就是两个对象引用），让它们同时指向这个链表的头节点。然后开始一个大循环，在循环体中，让指针p1每次向后移动1个节点，让指针p2每次向后移动2个节点，然后比较两个指针指向的节点是否相同。如果相同，则可以判断出链表有环，如果不同，则继续下一次循环。 等等等
这种方法的时间复杂度同样是0（n），但是双指针之外，没有额外使用存储空间，降低了空间复杂度。
四、代码实现
public static boolean isLinkCycle(Node head){
Node p1 = head;
Node p2 = head;
while(p2 != null && p2.next != null){
p1 = p1.next;
p2 = p2.next.next;
if(p1 == p2){
return true;
}
return false;
}
下一篇：
设计模式 (代理模式初探)