判断一个单链表有没有环?有三种方法。
方法一、穷举遍历
如上图,可见在遍历带环的链表时,同一个节点总会被遍历到两次。那么基于这一点出发,我们从头节点开始,遍历每个节点。在遍历的过程中,每遍历到一个新节点的时候,就回头把新节点之前的所有节点遍历一遍,然后看新节点的ID是否和之前节点的ID相同,如果相同,那么说明该节点被遍历过两次,链表有环,返回true or false。否则就继续遍历,然后重复这样的操作。
方法二、哈希集合+遍历
类似于方法一,这次我们不再比较新节点的ID与之前节点的ID,而是利用HashSet的不可重复性使用HashSet存储曾经遍历过的节点。每遇到一个新节点,就看HashSet是否包含这个节点,如果发现HashSet已经包含该节点,则说明链表有环;如果HashSet当中不包含节点,就把这个新节点存入HashSet,之后进入下一节点,继续重复刚才的操作。
方法三、快慢指针法
我们给定两个指针,一个快指针一个慢指针。两个指针同时遍历链表,快指针每次走两步,慢指针每次走一步。如果链表有环,那么最终快慢指针总会相遇。如果两种指针相遇,那么链表有环,返回true.其实快慢指针,为什么二指针总会相遇呢?这是一个数学问题。有兴趣的可以深入学习一下!
代码实现
public boolean hasCycle(ListNode head) {
HashSet<ListNode> set=new HashSet<ListNode>();//哈希法
while(head!=null){
if (set.contains(head)) {//如果set 可以加入head,返回true.如果不可以,返回false
return true;//
}
set.add(head);
head = head.next;
}
return false;
}
public boolean hasCycle(ListNode head) {
//快慢指针法
ListNode slowpoint=head;
ListNode fastpoint=head;
while(fastpoint!=null&&fastpoint.next!=null){//while()需要注意,不再使head!=null.当然是快节点以及快节点的下一个节点先到null。有可能是最后一步,有可能最后两步
slowpoint=slowpoint.next;//一次走一步
fastpoint=fastpoint.next.next;//一次走两步
if(slowpoint==fastpoint){
return true;
}
}
return false;
}