判断链表是否有环通常使用快慢指针法。以下是使用快慢指针法检测链表是否有环的步骤:
1. 初始化两个指针,`slow` 和 `fast`,都指向链表的头节点 `head`。
2. 在一个循环中,`slow` 指针每次移动一步,`fast` 指针每次移动两步。
3. 如果 `fast` 指针或 `fast->next` 为 `null`,说明链表无环,退出循环返回 `false`。
4. 如果 `slow` 和 `fast` 指针相遇,说明链表有环,退出循环返回 `true`。
该算法的时间复杂度为 O(n),空间复杂度为 O(1)。
下面是一个使用 Java 实现的示例代码:
```java
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
}
```
这段代码中,`ListNode` 是链表节点的定义,`hasCycle` 方法接收链表的头节点 `head` 作为参数,并返回一个布尔值,表示链表是否有环。