给定一个单链表的头节点 head
,判断链表中是否存在环。如果链表中存在环,则返回 true
,否则返回 false
。
注意: 链表节点定义如下:
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
我们使用快慢指针的方法来检测链表中是否存在环。具体步骤如下:
slow
和一个快指针 fast
,初始位置分别为链表头部。slow
移动一步,快指针 fast
移动两步。fast
指针最终会追上或者超过 slow
指针。/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
if (fast == slow) {
return true;
}
fast = fast.next.next;
slow = slow.next;
}
return false;
}
}