1
package 快慢指针遍历.q141_环形链表.f1;
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
package 快慢指针遍历.q141_环形链表.f1;
import java.util.HashSet;
import java.util.Set;
/**
* 哈希表 o(n)
*/
public class Solution {
public boolean hasCycle(ListNode head) {
Set<ListNode> nodesSeen = new HashSet<>();
while (head != null) {
if (nodesSeen.contains(head)) {
return true;
} else {
nodesSeen.add(head);
}
head = head.next;
}
return false;
}
}
2
package 快慢指针遍历.q141_环形链表.f2;
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
package 快慢指针遍历.q141_环形链表.f2;
/**
* 快慢指针 o(n)
*/
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;
}
}