Coding Interview Prep · 课时

使用 Floyd 算法检测环

Q: 「使用 Floyd 算法检测环」课时是免费的吗？

是的 — 「使用 Floyd 算法检测环」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。

Q: 「使用 Floyd 算法检测环」这节课中我会学到什么？

使用快慢指针检测环，找出环的入口，并从数学上证明算法的正确性。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

Q: 学习 Coding Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。

Q: 「使用 Floyd 算法检测环」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

Q: 我能在这节 Coding Interview Prep 课中编写并运行代码吗？

能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

使用快慢指针检测环，找出环的入口，并从数学上证明算法的正确性。

使用 Floyd 算法检测环 是 CoddyKit 上的免费 Coding Interview Prep 课时。这是第 3 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。

链表中的环是什么

链表中的环是指某个节点的 next 指针指回之前访问过的节点，从而形成无限循环。使用 while head 循环遍历这样的链表会永远运行下去。环检测是经典的面试问题，也是更高级指针算法的基础。

朴素方法会将所有访问过的节点存入集合，并检查节点是否存在于集合中，时间复杂度为 O(n)，空间复杂度为 O(n)。弗洛伊德算法可以在 O(n) 时间和O(1) 空间内解决同一问题，这正是面试官所期望的方案。

弗洛伊德慢速—快速指针算法

弗洛伊德环检测算法（「龟兔算法」）使用两个指针：slow 每次前进一个步骤，fast 每次前进两个步骤。如果不存在环，fast 会先到达 None。如果存在环，fast 最终会在环内追上 slow，两者在同一个节点相遇。相遇证明了环的存在。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

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

# Build: 3 -> 2 -> 0 -> -4 -> (back to 2)
nodes = [ListNode(v) for v in [3, 2, 0, -4]]
for i in range(3):
    nodes[i].next = nodes[i+1]
nodes[3].next = nodes[1]   # cycle: -4 -> 2

print(hasCycle(nodes[0]))  # True

慢速指针和快速指针为何总会相遇

直观地说：两个指针进入环后，它们之间的距离每一步都会变化 1（快速指针前进 2 步，慢速指针前进 1 步，因此每轮间距缩小 1）。最终间距会变为 0，也就是两者位于同一个节点。更正式地说，如果环的长度为 C，那么环内的最大间距是 C-1，而间距每一步缩小 1，因此两个指针会在它们都进入环后的 C 步以内相遇。

相遇前的总步数：最多为 O(n + C) = O(n)，因为 C <= n。

# Visualise convergence: simulate gap in cycle
cycle_length = 5
for start_gap in range(1, cycle_length + 1):
    gap = start_gap
    steps = 0
    while gap != 0:
        gap = (gap - 1) % cycle_length
        steps += 1
    print(f'Start gap {start_gap}: meet after {steps} step(s)')

寻找环的入口节点

检测到环后，弗洛伊德算法还可以找到入口节点（环开始的位置）。慢速指针和快速指针在环内相遇后，将一个指针重置到头节点，另一个保持在相遇点。然后让两个指针每次前进一个步骤。它们会恰好在环的入口节点相遇。这是因为从头节点到入口的距离，等于从相遇点到入口的距离（对环长度取模）。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def detectCycle(head):
    slow = fast = head
    # Phase 1: detect meeting point
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break
    else:
        return None  # no cycle
    # Phase 2: find entry
    pointer = head
    while pointer is not slow:
        pointer = pointer.next
        slow    = slow.next
    return pointer  # cycle entry node

nodes = [ListNode(v) for v in [3, 2, 0, -4]]
for i in range(3):
    nodes[i].next = nodes[i+1]
nodes[3].next = nodes[1]  # entry is nodes[1] (val=2)

entry = detectCycle(nodes[0])
print(entry.val)  # 2

入口节点的数学证明

设 F = 从头节点到环入口的距离，C = 环的长度，a = 从入口到环内相遇点的距离。相遇时：慢速指针走过了 F + a 步；快速指针走过了 F + a + n*C 步（领先 n 个完整环）。由于快速指针的速度是慢速指针的 2 倍：2(F+a) = F+a+nC → F = nC - a。这意味着从头节点到入口的距离，等于从相遇点到入口的距离（模 C）。将一个指针重置到头节点，并让两个指针各前进一步，它们最终会在入口节点相遇。

# Verify with our example: F=1 (head to node 2), C=3 (cycle: 2->0->-4->2), a=?
# Meeting inside cycle after F+a slow steps
# Let us measure a by counting from entry to meeting point
# In practice the code handles this automatically
F = 1   # head(3) to entry(2)
C = 3   # cycle length 2->0->-4
# n=1: F = 1*C - a => a = C - F = 3 - 1 = 2
a = C - F
print(f'F={F}, C={C}, a={a}')
print(f'After meeting, {F} more steps reach entry: {F == C - a or F % C == (C - a) % C}')

测量环的长度

获得环内的相遇点后（弗洛伊德算法的第一阶段），您可以测量环的长度：让一个指针保持不动，另一个指针不断前进，直到两者再次相遇。前进的步数就是环的长度。这对于明确要求计算环长度的问题很有用。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def cycle_length(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:  # found meeting point
            length = 1
            fast = fast.next
            while fast is not slow:
                fast = fast.next
                length += 1
            return length
    return 0  # no cycle

nodes = [ListNode(v) for v in [1, 2, 3, 4, 5]]
for i in range(4):
    nodes[i].next = nodes[i+1]
nodes[4].next = nodes[2]  # cycle: 3->4->5->3, length=3
print(cycle_length(nodes[0]))  # 3

快乐数（无需链表的环检测）

弗洛伊德算法并不局限于链表。LeetCode 202《快乐数》要求判断：不断将 n 替换为其各位数字的平方和，是否最终会得到 1。如果进入了不包含 1 的环，就会永远循环。您可以将这个过程建模为虚拟链表遍历，其中每个节点的「下一个节点」就是下一次计算得到的值，然后应用弗洛伊德算法检测环。

def isHappy(n):
    def next_val(x):
        total = 0
        while x:
            x, d = divmod(x, 10)
            total += d * d
        return total

    slow, fast = n, next_val(n)
    while fast != 1 and slow != fast:
        slow = next_val(slow)
        fast = next_val(next_val(fast))
    return fast == 1

print(isHappy(19))  # True  (1->81+1=82->68->100->1)
print(isHappy(2))   # False (enters cycle)

基于集合的朴素检测与弗洛伊德算法对比

基于集合的方法会将每个访问过的节点存入集合，并在访问前检查其是否存在。它的时间复杂度为 O(n)，空间复杂度为 O(n)。弗洛伊德算法的时间复杂度同样为 O(n)，但空间复杂度只有 O(1)，无需额外数据结构。在内存受限的环境中（例如嵌入式系统和操作系统内核），O(1) 空间保证十分重要。在您给出基于集合的方案后，面试官有时会进一步明确要求 O(1) 空间。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Naive O(n) space approach
def hasCycle_set(head):
    seen = set()
    while head:
        if id(head) in seen:
            return True
        seen.add(id(head))
        head = head.next
    return False

# Floyd's O(1) space approach
def hasCycle_floyd(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

print('Both implementations give the same result')

环检测的边界情况

需要处理三种边界情况。第一，空链表：head is None——弗洛伊德算法的循环条件 fast and fast.next 会立即退出，并返回 False。第二，无环的单节点链表：fast.next 为 None，循环退出并返回 False。第三，有环的单节点链表：节点的 next 指向自身——慢速指针和快速指针都从头节点开始；一步之后，快速指针前进两步后回到头节点，慢速指针前进一步后也回到头节点。因此在第一次迭代时两者就相等。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

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

# Edge cases
print(hasCycle(None))               # False: empty
node = ListNode(1)
print(hasCycle(node))               # False: single, no cycle
node.next = node
print(hasCycle(node))               # True: single node cycle

链表环 II：LeetCode 142

LeetCode 142《链表环 II》要求返回环开始位置的节点（如果没有环，则返回空值）。这是弗洛伊德两阶段算法的直接应用。面试官通常会把它作为基础环检测问题的后续问题。完整解决方案是：第一阶段找到环内的相遇点；第二阶段将一个指针重置到头节点，让两个指针一起向前移动，直到它们相遇——相遇点就是环的入口。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def detectCycle(head):
    slow = fast = head
    # Phase 1
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break
    else:
        return None
    # Phase 2
    ptr = head
    while ptr is not slow:
        ptr  = ptr.next
        slow = slow.next
    return ptr

nodes = [ListNode(v) for v in [1, 2, 3, 4, 5]]
for i in range(4):
    nodes[i].next = nodes[i+1]
nodes[4].next = nodes[2]  # cycle entry: node with val=3
entry = detectCycle(nodes[0])
print(entry.val)  # 3

弗洛伊德算法为何优于基于集合的方法

虽然两种方法的时间复杂度都是 O(n)，但在实际运行中常数因子有所不同。基于集合的方法必须对每个节点指针进行哈希处理（计算哈希值、查询哈希表并存储指针），而弗洛伊德算法只需进行指针解引用，因此每一步的开销低得多。更重要的是，O(1) 空间保证意味着弗洛伊德算法可以处理任意长度的链表，而不必担心内存耗尽。

在面试中主动提及这一空间优势，说明您不仅理解原始的大 O 表示法，还深入理解算法之间的权衡。

快速检查

请测试您对本课中数据结构与算法——编程面试准备相关概念的理解。

课程回顾

在本课中，您学到了：弗洛伊德慢速—快速指针算法可以在 O(n) 时间和 O(1) 空间内检测环，第二阶段（将一个指针重置到头节点，并让两个指针各前进一步）可以找到准确的环入口节点，以及同样的技术不仅适用于链表，也适用于任何将「下一个」定义为函数的隐式序列。接下来，我们将学习合并有序链表、在中点拆分链表，以及寻找倒数第 n 个节点。

常见问题解答