Fast and Slow Pointers

释义 Definition

“Fast and slow pointers”（快慢指针）是一种常见算法技巧：用两个指针在同一数据结构（常见于链表或数组）中以不同速度移动（通常一个每次走 1 步，另一个每次走 2 步），用来检测环（循环）、寻找环的入口、或定位中点等。

发音 Pronunciation (IPA)

/ˌfæst ən ˌsloʊ ˈpɔɪn.tɚz/

例句 Examples

I used fast and slow pointers to find the middle of the linked list.
我用快慢指针找到了链表的中点。

By applying fast and slow pointers, we can detect a cycle in O(n) time and O(1) extra space, and then compute the cycle’s entry point.
通过使用快慢指针，我们可以在 O(n) 时间、O(1) 额外空间内检测链表是否有环，并进一步求出环的入口位置。

词源 Etymology

该说法来自算法与面试语境中的直观命名：一个“快指针”跑得更快，一个“慢指针”跑得更慢。它与经典的 Floyd cycle-finding algorithm（弗洛伊德判圈算法）密切相关，也常被称为 “tortoise and hare”（龟兔赛跑）方法：如果存在环，快指针最终会在环内追上慢指针。

相关词 Related Words

• Floyd’s Cycle Detection
• Two-Pointer
• Runner Technique
• Linked List
• Cycle
• Pointer
• Middle Node
• Time Complexity

文学与著作中的用例 Literary / Notable Works

• Cracking the Coding Interview（Gayle Laakmann McDowell）中常以“runner technique / fast and slow pointers”讲解链表找中点与判环。
• Grokking the Coding Interview（Educative）将其作为模式（pattern）之一系统介绍，用于“Linked List Cycle”等题型。
• The Algorithm Design Manual（Steven S. Skiena）在讨论循环检测与指针技巧的相关内容时涉及与 Floyd 判圈思想一致的方法。