Floyd环检测

What · 是什么

Floyd 环检测(龟兔赛跑算法)用快慢两个指针检测链表或函数式序列是否有环：慢指针每步走 1，快指针每步走 2，若相遇则有环。相遇后慢指针重置到起点，两指针各走 1 步，再次相遇处即环起点。全程 O(n) 时间 O(1) 空间。也可推广到检测序列进入循环的周期。

Why · 为什么

How · 实现

伪代码

# 阶段1: 检测环
def has_cycle(head):
  slow = fast = head
  while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
      return True
  return False

# 阶段2: 找环起点
def cycle_start(head):
  slow = fast = head
  while fast and fast.next:
    slow = slow.next; fast = fast.next.next
    if slow == fast:
      break
  if not fast or not fast.next:
    return None
  slow = head
  while slow != fast:
    slow = slow.next; fast = fast.next
  return slow

Python 实现

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


def build_list(values, cycle_to=None):
    """建链表。cycle_to 为环入口结点下标(负索引从尾起), None 则无环。"""
    head = None
    nodes = []
    for v in values:
        nd = ListNode(v)
        nodes.append(nd)
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    if cycle_to is not None:
        nodes[-1].next = nodes[cycle_to]
    return nodes[0] if nodes else None


def has_cycle(head):
    """检测链表是否有环。"""
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False


def cycle_start(head):
    """返回环入口结点, 无环返回 None。"""
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break
    if fast is None or fast.next is None:
        return None
    slow = head
    while slow is not fast:
        slow = slow.next
        fast = fast.next
    return slow


def cycle_length(head):
    """环长(在环内数一圈)。无环返回0。"""
    entry = cycle_start(head)
    if entry is None:
        return 0
    cur = entry.next
    length = 1
    while cur is not entry:
        cur = cur.next
        length += 1
    return length


if __name__ == '__main__':
    # 无环
    h = build_list([1, 2, 3, 4])
    assert has_cycle(h) is False
    assert cycle_start(h) is None
    assert cycle_length(h) == 0

    # 有环: 1->2->3->4->2
    h2 = build_list([1, 2, 3, 4], cycle_to=1)
    assert has_cycle(h2) is True
    assert cycle_start(h2).val == 2
    assert cycle_length(h2) == 3

    # 环在头部: 1->1
    h3 = build_list([1], cycle_to=0)
    assert has_cycle(h3) is True
    assert cycle_start(h3).val == 1
    assert cycle_length(h3) == 1

    # 较长的链+环
    h4 = build_list(list(range(10)), cycle_to=4)  # 0..9, 9->4
    assert has_cycle(h4) is True
    assert cycle_start(h4).val == 4
    assert cycle_length(h4) == 6

    # 函数迭代序列环检测: x_{n+1} = (x*2+1) % 13 检测进入循环
    seen = {}
    x = 1
    seq = []
    while x not in seen:
        seen[x] = len(seq)
        seq.append(x)
        x = (x * 2 + 1) % 13
    # 用 Floyd 求序列环(对照)
    def f(v):
        return (v * 2 + 1) % 13
    slow = fast = 1
    # 找相遇
    for _ in range(30):
        slow = f(slow)
        fast = f(f(fast))
        if slow == fast:
            break
    print('seq head->cycle:', seq)
    print('meeting value  :', slow, ' cycle entry from dict:', x)

    print('cycle tests: h2 entry=2 len=3; h4 entry=4 len=6; all OK')
    print('All tortoise-hare tests passed!')

易错点

• 阶段1 循环条件 fast 与 fast.next 都要判 None, 否则无环链末尾访问 None.next 抛错
• 找环起点阶段 slow 重置到 head 后两指针等速(各走1), 别再让 fast 走 2 步
• 环长统计要先把入口存下来再转一圈, 别在找起点时顺手计数
• Python 用对象引用比较 `is` 而不是 ==(值相同但不同节点), 值重复时 == 会误判
• 序列/函数式检测: 快指针两步必须写 f(f(x)), 慢一步 f(x), 别混步数

例题

信源

• CP-Algorithms✓ https://cp-algorithms.com/others/tortoise_and_hare.html
• web✓ https://en.wikipedia.org/wiki/Cycle_detection
• web✓ https://leetcode.cn/problems/linked-list-cycle-ii/