环形链表
一,题目描述
给定一个链表的头节点,判断链表中是否存在环。存在返回true,不存在返回false。
二,解题思路
如果链表无环,遍历后最终都会指向null。如果有环,会重复遍历。
三、解题方法
方法1:遍历
创建一个set集合,遍历整个链表。并存入集合中,当链表有环时,由于set集合的特性。就可一判断是否有环。
代码实现
public class Solution {
public boolean hasCycle(ListNode head) {
Set<ListNode> set = new HashSet<ListNode>();
while(head != null){
if(!set.add(head)){
return true;
}
head = head.next;
}
return false;
}
}
方法2:快慢指针
使用快慢指针,慢指针步长为1,快指针步长为2,如果有环,快慢指针总会相遇。如果无环,最终快指针会首先指向null。
代码实现:
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null || head.next == null){
return false;
}
ListNode low = head;
ListNode fast = head.next;
while(low != fast){
if(fast==null || fast.next==null){
return false;
}
low = low.next;
fast = fast.next.next;
}
return true;
}
}
标签:head,return,环形,fast,next,链表,null
From: https://www.cnblogs.com/zjjtt/p/16786519.html