141. 环形链表
查看题目简单
链表
高频
解法一：双指针
时间复杂度：O(n) | 空间复杂度：O(1) | 推荐使用
动画演示
准备就绪 - 输入链表值和环的位置
代码实现
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;
}
}
时间复杂度：O(n)
空间复杂度：O(1)
双指针算法（快慢指针）：
1. 初始化两个指针，slow（慢指针）和fast（快指针），都指向链表头部
2. slow指针每次移动一步，fast指针每次移动两步
3. 如果链表中存在环，fast指针最终会追上slow指针
4. 如果fast指针到达链表末尾（null），则链表无环
该算法的时间复杂度为O(n)，空间复杂度为O(1)，是检测链表是否有环的最优解法之一。