《链表篇》---环形链表
题目传送门
方法一:哈希表
public class Solution {
public boolean hasCycle(ListNode head) {
Set<ListNode> visited = new HashSet<ListNode>();
while(head != null){
visited.add(head);
head = head.next;
if(visited.contains(head)){
return true;
}
}
return false;
}
}
方法二:快慢指针
1.如果没有节点或只有一个节点,返回false。
2.定义一个快指针,一个慢指针。在快指针不等于慢指针的情况下,慢指针走一步,快指针走两步。
3.若快指针走到了最后一个节点,或者最后的空节点。说明没有环,返回false。
4.若有环,则快指针必定会被慢指针追上。因此若相等则返回true。
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null || head.next == null){
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while(slow != fast){
if(fast == null || fast.next == null){
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
}