【大厂高频算法题】判断链表中是否有环
题目:判断给定的链表中是否有环。如果有环则返回true,否则返回false。 难度:简单
代码:
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode pos = head;
// 哈希表记录访问过的结点
Set<ListNode> set = new HashSet<>();
while (pos != null) {
// 判断结点是否被访问
if (set.contains(pos)) {
return true;
} else {
// 结点记录添加到哈希表中
set.add(pos);
}
// 遍历
pos = pos.next;
}
return false;
}
}
第二种方式:
public class Solution {
public boolean hasCycle(ListNode head) {
//先判断链表为空的情况
if(head == null)
return false;
//快慢双指针
ListNode fast = head;
ListNode slow = head;
//如果没环快指针会先到链表尾
while(fast != null && fast.next != null){
//快指针移动两步
fast = fast.next.next;
//慢指针移动一步
slow = slow.next;
//相遇则有环
if(fast == slow)
return true;
}
//到末尾则没有环
return false;
}
}