Java实现判断链表是否存在环

题目

存在环,2节点 在这里插入图片描述   不存在环 在这里插入图片描述 节点数据结构
public class ListNode {
 public int val;
 public ListNode next;
 public ListNode() {}
 public ListNode(int val) { this.val = val; }
 public ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

实现方法

1、快慢指针

快指针跑的快,再循环中每次走两步,慢指针走一步,若存在封闭环,快指针一定会追上慢指针,若不准走,则在快指针到达末尾是就结束
// 环形链表--快慢指针
 //时间复杂度:O(n)
 //空间复杂度:O(1)
public  boolean iscycle(LinkNode head){
   LinkNode slow = head;
   LinkNode fast = head.next;
   while(slow!=fast){
      if(slow.next==null||fast.next==null){
         return  false;
      }
      slow = slow.next;
      fast = fast.next.next;
   }
   return true;
}

2、哈希表法

引用哈希表,若已经存在此节点,得返回true,有环存在,若哈希表中不存在,则将该节点放入哈希表中,若最后还没遇到相同的节点,则说明没有环。 但此方法空间复杂度高
// 环形链表--哈希表
 //时间复杂度:O(n)
 //空间复杂度:O(n)
public boolean iscycletwo(LinkNode head) {
   Set<LinkNode> set = new HashSet<LinkNode>();
   while(head!=null) {
      if (!set.add(head)) {
         return true;
      }else{
         head=head.next;
      }
   }
   return false;
}
 
正文到此结束
Loading...