java 给定一个链表,判断链表中是否有环。
时间: 2023-07-17 09:02:07 浏览: 108
判断单链表中是否存在环
可以使用快慢指针来判断链表中是否有环。定义两个指针,一个指针每次向前移动一个节点,而另一个指针每次向前移动两个节点。如果链表中存在环,那么这两个指针最终会相遇;如果链表中不存在环,那么快指针最终会到达链表的尾部。
下面是一个示例的 Java 代码实现:
```java
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;
}
```
这段代码中,我们首先判断链表是否为空或者只有一个节点,如果是的话,直接返回 false。然后定义两个指针 slow 和 fast,分别指向链表的头节点和头节点的下一个节点。在循环中,我们不断将 slow 指针向后移动一个节点,fast 指针向后移动两个节点。如果链表中存在环,那么快指针最终会追上慢指针,它们会相遇;如果链表中不存在环,那么快指针最终会到达链表的尾部,循环结束。最后,我们返回一个布尔值来表示链表中是否有环。
阅读全文