转载

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;
}

正文到此结束