如何判断一个单链表有环?

判断一个单链表有没有环?有三种方法。

如何判断一个单链表有环?

方法一、穷举遍历

如上图,可见在遍历带环的链表时,同一个节点总会被遍历到两次。那么基于这一点出发,我们从头节点开始,遍历每个节点。在遍历的过程中,每遍历到一个新节点的时候,就回头把新节点之前的所有节点遍历一遍,然后看新节点的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;   
}

如何判断一个单链表有环?

上一篇:剑指 Offer 07. 重建二叉树


下一篇:git 命令的使用