环形链表
Linked List Cycle
本机进度仅保存在当前浏览器
题目描述
给你一个链表的头节点 head，判断链表中是否有环。链表中某节点的 next 指针回指到之前出现过的节点即构成环。要求 O(1) 空间。
示例：3 -> 2 -> 0 -> -4，尾节点指向下标 1 的节点，存在环，输出 true。
解题思路
- 哈希表记录访问过的节点是平凡解，但要 O(n) 空间。
- Floyd 判圈（快慢指针）：慢指针每次走一步，快指针每次走两步。
- 无环时快指针先到尾部；有环时快指针会在环内"追上"慢指针，两者相遇即有环。
- 直觉：相对速度为每步一格，快指针相对慢指针在环内逐格逼近，必然相遇而不会跳过。
参考实现
查看参考实现Python · 建议先自行作答
def hasCycle(head):
# 快慢指针，相遇即有环
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False