这篇文章上次修改于 1108 天前,可能其部分内容已经发生变化,如有疑问可询问作者。 >给定一个链表,判断链表中是否有环。 [leetcode141链接](https://leetcode-cn.com/problems/linked-list-cycle/?utm_source=LCUS&utm_medium=ip_redirect&utm_campaign=transfer2china) ##### 示例 [pic](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/07/circularlinkedlist.png) 输入:head = [3,2,0,-4], pos = 1 输出:true 解释:链表中有一个环,其尾部连接到第二个节点。 ##### 思路1,用hashset判断。 ```java static boolean hasCycle(ListNode head) { HashSet nodeSet = new HashSet<>(); while (head != null){ if(nodeSet.contains(head)){ return true; } nodeSet.add(head); head = head.next; } return false; } ``` ##### 思路2:快慢指针,直到指针相遇 ``` java public class Solution { public boolean hasCycle(ListNode head) { ListNode slow =head ; ListNode fast = head == null ? null :(head.next == null ? null:head.next.next); while (slow != null && fast != null){ if(slow.equals(fast)){ return true; } slow = slow.next; fast =fast.next == null ? null:fast.next.next; } return false; } } ``` ##### 复杂度O(N) 总结,链表类的思路都不是很复杂,难得是指针的写法和判断,要多加熟练
没有评论