LeetCode中怎么判断链表是否有环

在LeetCode的算法题目中，链表是一个常见的数据结构。链表中的环（Cycle）是指链表的某个节点的next指针指向了链表中之前的某个节点，从而形成了一个环状结构。判断链表是否有环是一个经典的面试题，本文将详细介绍如何在LeetCode中判断链表是否有环，并分析常见的解题思路和算法。

1. 问题描述

给定一个链表，判断链表中是否有环。如果链表中有某个节点可以通过连续跟踪next指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数pos来表示链表尾连接到链表中的位置（索引从0开始）。如果pos是-1，则在该链表中没有环。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

2. 解题思路

判断链表是否有环的常见方法有两种：哈希表法和快慢指针法。下面我们将分别介绍这两种方法。

2.1 哈希表法

哈希表法的思路是遍历链表中的每个节点，并将每个节点的引用存储在哈希表中。如果在遍历过程中发现某个节点的引用已经存在于哈希表中，则说明链表中存在环；否则，链表中没有环。

算法步骤：

1. 初始化一个空的哈希表visited。
2. 遍历链表中的每个节点：
   • 如果当前节点已经存在于visited中，则链表中存在环，返回true。
   • 否则，将当前节点添加到visited中。
3. 如果遍历完整个链表都没有发现重复的节点，则链表中没有环，返回false。

代码实现：

def hasCycle(head):
    visited = set()
    while head:
        if head in visited:
            return True
        visited.add(head)
        head = head.next
    return False

时间复杂度： O(n)，其中n是链表中的节点数。最坏情况下需要遍历整个链表。

空间复杂度： O(n)，哈希表存储了链表中的所有节点。

2.2 快慢指针法

快慢指针法是一种更高效的判断链表是否有环的方法。该方法使用两个指针，一个快指针和一个慢指针。快指针每次移动两步，慢指针每次移动一步。如果链表中存在环，快指针最终会追上慢指针；如果链表中没有环，快指针会到达链表的末尾。

算法步骤：

1. 初始化两个指针slow和fast，都指向链表的头节点head。
2. 使用一个循环遍历链表：
   • 如果fast或fast.next为None，则链表中没有环，返回false。
   • 否则，slow指针移动一步，fast指针移动两步。
   • 如果slow和fast指针相遇，则链表中存在环，返回true。
3. 如果循环结束仍未相遇，则链表中没有环，返回false。

代码实现：

def hasCycle(head):
    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

时间复杂度： O(n)，其中n是链表中的节点数。最坏情况下需要遍历整个链表。

空间复杂度： O(1)，只使用了两个额外的指针。

3. 算法比较

4. 总结

判断链表是否有环是一个经典的算法问题，LeetCode中也有相关的题目。本文介绍了两种常见的解题方法：哈希表法和快慢指针法。哈希表法简单直观，但需要额外的空间；快慢指针法空间复杂度低，效率高，但实现稍微复杂一些。在实际应用中，可以根据具体需求选择合适的方法。

在LeetCode中，推荐使用快慢指针法来解决链表是否有环的问题，因为它不仅效率高，而且空间复杂度低，适合处理大规模数据。希望本文能帮助你更好地理解和掌握判断链表是否有环的算法。