如何判断一个链表是否有环？

推荐答案

// www.javascriptcn.com code example
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def hasCycle(head: ListNode) -> bool:
    if not head or not head.next:
        return False
    
    slow = head
    fast = head.next
    
    while slow != fast:
        if not fast or not fast.next:
            return False
        slow = slow.next
        fast = fast.next.next
    
    return True

本题详细解读

1. 问题描述

判断一个链表是否有环，即链表中是否存在一个节点，通过连续跟踪 next 指针再次到达该节点。

2. 解题思路

使用快慢指针（Floyd's Tortoise and Hare Algorithm）来判断链表是否有环。快指针每次移动两步，慢指针每次移动一步。如果链表中有环，快指针最终会追上慢指针；如果没有环，快指针会到达链表末尾。

3. 代码解析

• ListNode 类：定义了链表节点的结构，包含 val 和 next 两个属性。
• hasCycle 函数：接受链表的头节点 head 作为参数，返回一个布尔值表示链表是否有环。
  • 边界条件：如果链表为空或只有一个节点，直接返回 False。
  • 初始化指针：slow 指针指向头节点，fast 指针指向头节点的下一个节点。
  • 循环判断：在 slow 和 fast 不相等的情况下，移动 slow 指针一步，fast 指针两步。如果 fast 或 fast.next 为 None，说明链表无环，返回 False。
  • 返回结果：如果 slow 和 fast 相等，说明链表有环，返回 True。

4. 复杂度分析

• 时间复杂度：O(n)，其中 n 是链表中节点的数量。最坏情况下，快指针和慢指针会遍历整个链表。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。