题解 | #判断链表中是否有环#
判断链表中是否有环
https://www.nowcoder.com/practice/650474f313294468a4ded3ce0f7898b9
import java.util.*; /** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ // public class Solution { // double indexes // public boolean hasCycle(ListNode head) { // if(head==null||head.next==null||head.next.next==null){ // return false; // } // ListNode slow, fast; // slow = head; // fast = head; // for(int i=0;i<10001;i++){ // fast = fast.next; // if(slow==fast){ // return true; // } else if(fast==null){ // return false; // } // fast = fast.next; // if(slow==fast){ // return true; // } else if(fast==null){ // return false; // } // slow = slow.next; // if(slow==fast){ // return true; // } // } // return false; // } // } public class Solution{ // hash map public boolean hasCycle(ListNode head){ HashSet<ListNode> set = new HashSet<>(); while(head!=null){ if(set.contains(head)){ return true; } set.add(head); head = head.next; } return false; } }
法1:快慢指针,追及的思想(非常优雅)。我的方法似乎代码有些多虑了,循环结束条件只需要考虑fast指针会不会走到null就行了。
法2:哈希表。要点:HashSet<ListNode> set = new HashSet<>(); 的定义,以及set.contains()方法的调用,set.add()方法的调用。