检测链表是否形成环的算法解析 | 快慢指针法详解

检测链表是否形成环（即链表是否有环）是一个经典的算法问题。我们可以使用“快慢指针”（也称为“龟兔赛跑”算法）来解决这个问题。这个算法的时间复杂度是 O(n)，空间复杂度是 O(1)，非常高效。

算法思路：

1. 使用两个指针，一个快指针（fast）和一个慢指针（slow）。
2. 慢指针每次移动一步，快指针每次移动两步。
3. 如果链表中有环，快指针最终会追上慢指针（即两者会相遇）。
4. 如果快指针到达链表末尾（即 fast 或 fast.next 为 null），则链表无环。

代码实现（JavaScript）：

function hasCycle(head) {
    if (!head || !head.next) {
        return false; // 链表为空或只有一个节点，不可能有环
    }

    let slow = head;
    let fast = head;

    while (fast && fast.next) {
        slow = slow.next; // 慢指针移动一步
        fast = fast.next.next; // 快指针移动两步

        if (slow === fast) {
            return true; // 快慢指针相遇，链表有环
        }
    }

    return false; // 快指针到达链表末尾，链表无环
}

解释：

• slow 和 fast 都从链表的头节点 head 开始。
• slow 每次移动一步，fast 每次移动两步。
• 如果链表有环，fast 最终会追上 slow，此时 slow === fast，返回 true。
• 如果 fast 或 fast.next 为 null，说明链表无环，返回 false。

示例：

假设有一个链表 1 -> 2 -> 3 -> 4 -> 5 -> 2（节点 5 指向节点 2，形成环），调用 hasCycle(head) 将返回 true。

复杂度分析：

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

这个算法是检测链表是否有环的最优解之一，既高效又简洁。