JAVA:环链表（判断单链表是否存在环）

小咪咪 2022-06-17 05:13 219阅读 0赞

【题目描述】Given a linked list, determine if it has a cycle in it.  
Follow up:  
Can you solve it without using extra space?  
给定单链表，判断是否存在环？不适用额外空间

> 【知识点】：  
> 环链表：从判断一个单链表是否存在循环而扩展衍生的问题，有则称之为有环链表问题。  
> 【解决方法】：  
> 1.将所有遍历过的节点用某个结构存储起来，然后遍历每个节点，都在这个结构中查找是否遍历过。如果有遍历过，那就证明存在环。  
> 这个结构，可以是hash，hash中的值存储的是节点的内存地址，  
> 因此查找的操作所需时间O(1)  
> 遍历的操作所需时间O(n)  
> hash存储空间所需额外的O(n)  
> 【时间复杂度为O(n)，空间复杂度为O(n)】  
> *但是：因为使用了某结构存储，所以，违反了题目要求，要叉掉*  
> 2.最佳方案  
> 【快慢指针】：需要两个指针，一个快指针：每次走两步，一个慢指针：每次走一步。  
> 如果快慢指针能够相遇（如果快指针能够追上慢指针)，就证明有环。  
> *但是！！！这个方法存在问题。如果链表够长，而环又足够小，那么快指针将永远不会追上慢指针*  
> *所以，快慢指针只适合用于环出现在链表尾部的情况，也就是单链表环的问题，而无法解决链表存在循环的问题。*

在java中构造单链表

public class ListNode{
     int val;
     ListNode next;
     ListNode(int x){
     val=x;//头节点
     next=null;
    }
    }

【代码实现】

public class Link_list_circle{
    
     public boolean hascycle(ListNode head){
      //快慢指针
      ListNode slow,fast;
      slow=fast=head;
      while(fast!=null&&fast.next!=null){
      slow=slow.next;
      fast=fast.next.next;
      if(fast==slow)return ture;
    }
       return false;
    }
    
    
    }