关于判断链表是否有环的多种解法
今天闲来无事看到一个小米面试视频，其中问到了面试者除了快慢指针之外的解法，
博主觉得很有意义，于是总结了一下。
1. 定义快慢指针
go源代码：
func hasCycle(head *ListNode) bool {
if head == nil || head.Next == nil {
return false
}
slow := head
fast := head.Next
for slow != fast {
if fast == nil || fast.Next == nil {
return false
}
slow = slow.Next // 慢指针走一步
fast = fast.Next.Next // 快指针走两步
}
return true
}
2. 哈希表 / 集合存储访问过的节点
遍历链表时，将每个节点存入哈希表 / 集合中
每次访问新节点前，先检查该节点是否已在集合中
如果存在，则说明有环；如果遍历结束仍未重复，则无环
时间复杂度 O (n)，空间复杂度 O (n)
python源代码：
def hasCycle(head):
visited = set()
current = head
while current:
if current in visited:
return True
visited.add(current)
current = current.next
return False
3. 修改节点值标记访问过的节点
遍历链表时，将访问过的节点值修改为一个特殊标记（如 None 或特定值）
当遇到值为特殊标记的节点时，说明有环
缺点是会修改原链表数据
时间复杂度 O (n)，空间复杂度 O (1)
python源代码：
def hasCycle(head):
current = head
while current:
if current.val is None: # 假设原链表中没有None值
return True
current.val = None # 标记为已访问
current = current.next
return False
4. 递归回溯标记法
利用递归栈回溯的特性，在递归过程中标记访问过的节点
递归返回时恢复节点状态（可选）
时间复杂度 O (n)，空间复杂度 O (n)（递归栈开销）
python源代码：
def hasCycle(head):
if not head:
return False
if head.val is None: # 遇到已标记的节点，说明有环
return True
head.val = None # 标记当前节点
result = hasCycle(head.next)
# 可选：恢复节点值
# head.val = original_value
return result
5. 总结
1. 快慢指针法（Floyd 判圈算法）
核心原理：通过两个移动速度不同的指针（慢指针一次走 1 步，快指针一次走 2 步）遍历链表，若存在环，两指针最终会在环内相遇；若不存在环，快指针会先到达链表尾部。
优点：
时间复杂度 O (n)，只需一次遍历即可完成判断
空间复杂度 O (1)，不需要额外存储空间，仅使用两个指针
不修改链表原有数据，是无损操作
缺点：
逻辑相对复杂，需要理解指针相遇的原理
无法直接定位环的入口点（需额外步骤）
适用场景：对空间复杂度要求严格，且不希望修改原链表的场景，是实际开发中的首选方案。
2. 哈希表 / 集合存储法
核心原理：利用哈希表 / 集合存储已访问过的节点，每次访问新节点时检查是否已在集合中，若存在则说明有环。
优点：
逻辑简单直观，容易理解和实现
不仅能判断是否有环，还能定位环的入口点（第一个重复出现的节点）
缺点：
空间复杂度 O (n)，需要存储所有访问过的节点
对于大型链表，额外的空间开销可能成为问题
适用场景：对空间复杂度要求不高，更注重代码可读性和实现便捷性的场景。
3. 修改节点值标记法
核心原理：遍历过程中修改已访问节点的值为特殊标记，当再次遇到该标记时说明有环。
优点：
空间复杂度 O (1)，不需要额外存储空间
实现逻辑简单直接
缺点：
会永久性修改链表节点的值，破坏原数据（不可逆操作）
依赖链表中不存在的特殊标记值，存在潜在冲突风险
适用场景：仅适用于可以修改原链表且对数据完整性要求不高的特殊场景，实际开发中很少使用。
4. 递归回溯标记法
核心原理：利用递归调用栈的特性，在递归过程中标记节点，回溯时可选择恢复节点状态。
优点：
可以通过回溯恢复节点原值，避免永久修改数据
逻辑上体现了深度优先遍历的思想
缺点：
空间复杂度 O (n)，递归调用栈的深度等同于链表长度
对于过长的链表可能导致栈溢出（stack overflow）
实现相对复杂，需要处理递归边界和状态恢复
适用场景：几乎不用于实际生产环境，更多是理论上的实现方式，仅在特殊递归场景下可能考虑。
评论区