链表 · 快慢指针

从 LC 141 判断链表是否有环开始：Floyd 龟兔指针如何用 O(1) 额外空间解决"找环 / 找环入口 / 找中点"这一族问题。

Medium预计阅读 45 分钟更新于 2026-05-18

1. 核心原理

快慢指针（two-pointer fast-slow，又称 Floyd 龟兔算法）要解决的问题模板长这样："给一个单链表，问它是否有环 / 环入口在哪 / 中点是谁 / 倒数第 n 个是谁"——只能单向走、不能回头的链表，靠两个游标按不同速度沿 next 移动，从相对位置或相对速度提取结构信息。

朴素思路是开 O(n) 的 hashset 记录访问过的节点，再来重复的就是环。逻辑没毛病，但空间是硬伤：链表如果来自流式数据源、或者节点本身是数据库 record / 文件句柄，开 set 等于把整个流缓存到内存且延长引用生命周期。我们只想要"是否有环"一个 bit 的信息，凭什么要付 O(n) 空间。Floyd 龟兔算法把这件事降到 O(1) 额外空间，并且同一套游标顺手解决找中点、找环入口、找倒数第 n 个节点等一系列衍生问题。

Floyd 龟兔的相遇必然性

把链表分成两段：从 head 到环入口的"尾巴"长度记为 F（也常写作 a），环本身的长度记为 L（也常写作 C）。

派两个游标：slow 每步走 1 节点（slow = slow.next），fast 每步走 2 节点（fast = fast.next.next）。

无环时：fast 会先撞到 null（每轮 fast 或 fast.next 至少有一个为 null），循环退出。
有环时：两个游标都会进入环。一旦都进入环，fast 每轮比 slow 多走 1 步，相对距离每轮 +1 然后 mod L。相对距离从某个初值（≤ L）出发，每轮 +1，最多 L 轮后必为 0——即 fast 追上 slow。

所以只要环存在，两个游标必然在进入环后的 L 轮内相遇。

找环入口：从 `2(F + a) = F + a + nC` 推出 `F = nC − a`

设第一次相遇时 slow 走了 F + a 步（F 是头到环口距离，a 是相遇点在环内距环口的距离，0 ≤ a < L，这里 L = C）。同一时刻 fast 走了 2(F + a) 步。fast 比 slow 多走了若干圈，于是：

2(F + a) = F + a + nC      （n ≥ 1）
       F + a = nC
           F = nC − a = (n − 1)C + (C − a)

这个等式说明：从 head 走 F 步到达环入口；同时从相遇点走 nC − a 步也到达环入口（多绕的 (n − 1)C 不改变位置，从相遇点再走 C − a 就是环口）。

工程意义：让一个游标回到 head，另一个留在相遇点，两者都每次走 1 步，再次相遇时就是环入口。这是 LC 142 的 Floyd 第二阶段。

找中点：fast 走两倍速时 slow 恰好停在一半

把 fast 走两倍速换个角度看：fast 走完链表时，slow 恰好走完了一半。同一套游标顺手就能找链表中点——fast 走到末尾时，slow 停在中点。链表奇偶长度会影响"中点取前还是取后"：

目标	循环条件	偶数 `[1,2,3,4]` 返回
取后中点（LC 876 定义）	`while fast and fast.next`	`3`（下标 2，后半段第一个）
取前中点（用于切链反转）	`while fast.next and fast.next.next`	`2`（下标 1，前半段最后一个）

奇数长度时两者结果相同（都是正中间）。LC 234 / LC 143 这类"反转后半段再比对"的题需要取前中点。

一族同骨架的题

快慢指针解决的一族题共用 slow 走 1 步 / fast 走 2 步的骨架，区别只在退出循环后做什么：

题型	退出后的操作
判环	相遇就返回 `true`，走完链返回 `false`
找环入口	相遇后启动第二阶段同步走
找中点	直接返回 `slow`
倒数第 n 个	改成"固定间距 N"：fast 先走 n 步，slow 再同步走

2. 通用模板

快慢指针的最小骨架是 while fast and fast.next: slow = slow.next; fast = fast.next.next——确保 fast.next.next 可访问。剩下的题目逻辑挂在循环体里或循环结束之后。下面给三个语言的核心模板：模板 A 判环、模板 B 找环入口、模板 C 找中点。

模板 A：判环

def has_cycle(head):
    """返回链表是否有环。Floyd 龟兔，O(n) 时间 / O(1) 空间。"""
    slow = fast = head
    while fast and fast.next:           # fast 每轮要走 2 步，两个 next 都得在
        slow = slow.next
        fast = fast.next.next
        if slow is fast:                # 引用相等（is），不是值相等
            return True
    return False

public boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;  // 引用相等，不是 .equals
    }
    return false;
}

bool hasCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;  // 指针相等
    }
    return false;
}

模板 B：找环入口

def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:                # 第一阶段相遇
            ptr = head                  # 第二阶段：一个回到 head
            while ptr is not slow:
                ptr = ptr.next
                slow = slow.next
            return ptr                  # 同时到达的点就是环入口
    return None

public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {              // 第一阶段相遇
            ListNode ptr = head;          // 第二阶段
            while (ptr != slow) {
                ptr = ptr.next;
                slow = slow.next;
            }
            return ptr;
        }
    }
    return null;
}

ListNode* detectCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {              // 第一阶段相遇
            ListNode* ptr = head;        // 第二阶段
            while (ptr != slow) {
                ptr = ptr->next;
                slow = slow->next;
            }
            return ptr;
        }
    }
    return nullptr;
}

模板 C：找中点（取后版本）

def middle_node(head):
    """返回链表中点。偶数长度时返回后半段第一个节点（LC 876 的定义）。"""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

public ListNode middleNode(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

ListNode* middleNode(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

三个模板共享同一份骨架。几点要说明：

循环条件 while fast and fast.next：下一轮要算 fast.next.next，必须保证 fast.next 本身不是 null。while fast 在 fast.next == null 时会抛 NPE / segfault。
相等判定用引用 / 指针相等（Python is、Java/C++ ==），不是值相等。链表 [1,1,1] 没环时节点值都相等，但只有真环才让两个游标落到同一对象。
取前中点：把模板 C 的循环条件改成 while fast.next and fast.next.next——fast 还要能走两步才进入循环，slow 会停在前半段最后一个节点。LC 234 / LC 143 用这版。
空链表 / 单节点：模板对所有边界都自洽。head is null 时 fast 也是 null，循环不进；单节点 head.next is null 时同理。

3. 母题精讲

LeetCode 141. Linked List Cycle

链接：LeetCode 141

题目（中文翻译）：给一个单向链表的头节点 head，判断这个链表里是否存在环——即从某个节点出发，沿 next 指针走，最终能回到已访问过的节点。存在环返回 true，否则返回 false。

数据范围：

链表节点数：0 到 10⁴
节点值：−10⁵ 到 10⁵
环存在时由内部参数 pos 指明尾节点指向的下标（仅用于构造测试用例，函数本身拿不到 pos）

示例：

输入：head = [3, 2, 0, -4], pos = 1
输出：true
解释：尾节点 -4 的 next 指回下标 1（值 2），形成环 2 → 0 → -4 → 2 → ...

输入：head = [1], pos = -1
输出：false
解释：单节点链表，next 是 null，没有环。

暴力解：哈希集合记录访问过的节点

直觉解是从头开始走，把每个走过的节点存进一个 set。下一步要走的节点如果已经在 set 里，说明绕回来了，存在环；如果走到 null，说明没环。

class Solution:
    def hasCycle_hashset(self, head: 'ListNode') -> bool:
        seen = set()
        node = head
        while node:
            if node in seen:        # 已访问过 → 有环
                return True
            seen.add(node)          # 存的是节点对象的身份，不是值
            node = node.next
        return False                # 走到 null → 无环

public boolean hasCycleHashset(ListNode head) {
    Set<ListNode> seen = new HashSet<>();
    ListNode node = head;
    while (node != null) {
        if (!seen.add(node)) {      // add 返回 false 表示已存在
            return true;
        }
        node = node.next;
    }
    return false;
}

bool hasCycleHashset(ListNode* head) {
    unordered_set<ListNode*> seen;
    for (ListNode* node = head; node != nullptr; node = node->next) {
        if (!seen.insert(node).second) {   // insert 返回 pair，second=false 表示已存在
            return true;
        }
    }
    return false;
}

时间 O(n)，空间 O(n)——每个节点入一次 set。LC 141 直接 AC，但空间是硬伤：工程里链表可能来自 streaming 数据源，开 O(n) 的 hashset 等价于把整个流缓存到内存；如果节点是数据库 record 或文件句柄，存进 set 会延长引用生命周期，Java / Go 里 GC 不能回收。目标是 O(n) 时间 + O(1) 额外空间的 Floyd 龟兔解——模板 A 即标准答案。

Floyd 龟兔的步进可视化

走一遍 1 → 2 → 3 → 4 → 5 → 回到 3 这条有环链表（环长 L = 3，环入口在下标 2）。把链表节点平铺成数组展示，红色表示 slow 当前所在节点，金色表示 fast：

hasCycle: 1 → 2 → 3 → 4 → 5 → (next = node[2])

链表节点平铺成数组，每轮 slow 走 1 步、fast 走 2 步，相遇即有环

Step 1 / 4初始：slow = fast = head（下标 0，值 1）

index

01234

value

↑slowfast

slow 所在节点fast 所在节点相遇（slow == fast）其他节点

01/04

每轮两个游标都在前进，相遇就停。整个过程没开新数组、没开 set——只有两个指针变量。§4.1 给完整代码。

4. 例题（三道）

下面三道题按"难度递增"排：判环 → 找环入口 → 找中点。每道末尾给一个 follow-up 直接续到下一题。

4.1 LC 141 环形链表

链接：LeetCode 141

题意：给一个单向链表头节点 head，判断链表中是否存在环。函数只能拿到 head，没法直接读到环的结构。

数据范围：

链表节点数：0 到 10⁴
节点值：−10⁵ 到 10⁵

示例：

输入：head = [3, 2, 0, -4], pos = 1
输出：true

输入：head = [1, 2], pos = 0
输出：true

输入：head = [1], pos = -1
输出：false

直接套模板 A：

class Solution:
    def hasCycle(self, head: 'ListNode') -> bool:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                return True
        return False

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
}

class Solution {
public:
    bool hasCycle(ListNode* head) {
        ListNode *slow = head, *fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) return true;
        }
        return false;
    }
};

几个细节值得讲：

第一，循环条件为什么是 fast and fast.next？因为下一轮要算 fast.next.next，需要保证 fast.next 本身不是 null。如果只写 while fast，当 fast.next == null 时 fast.next.next 会抛 NPE。

第二，比较为什么用 is（Python）/ ==（Java/Go 对引用）？两个指针比较的是"指向同一个节点对象"，而不是"节点存的值相等"。链表里可能多个节点值相同（比如 [1, 1, 1]），但只有真的环才会让两个指针落到同一个对象。

第三，slow == head == fast 初始化时为什么不会立刻返回 true？因为我们的相等判定写在"走了一步之后"。第 0 轮不判，先走，再判。这样 0 节点和 1 节点链表（必然无环）能正确返回 false。

复杂度：时间 O(n)，空间 O(1)。这里 n 是链表节点数；有环时上界是 a + L（尾巴长度 + 环长），仍然是 O(n)。

Follow-up：判出来"有环"只是第一步。如果题目要求返回环的入口节点呢？

4.2 LC 142 环形链表 II

链接：LeetCode 142

题意：给一个单向链表头节点 head，如果链表存在环，返回环开始入环的第一个节点；如果不存在环，返回 null。要求 O(1) 额外空间。

数据范围：

链表节点数：0 到 10⁴
节点值：−10⁵ 到 10⁵

示例：

输入：head = [3, 2, 0, -4], pos = 1
输出：节点 2（下标 1 的节点）
解释：环的入口是值为 2 的节点。

输入：head = [1], pos = -1
输出：null

§2 已经把数学推过：第一阶段两指针相遇后，让一个指针回到 head，两个指针同时每步走 1，再次相遇时就是环入口。

class Solution:
    def detectCycle(self, head: 'ListNode') -> 'ListNode':
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:                        # 第一阶段相遇
                ptr = head
                while ptr is not slow:              # 第二阶段同步走
                    ptr = ptr.next
                    slow = slow.next
                return ptr
        return None                                 # 无环

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}

class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        ListNode *slow = head, *fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {                       // 第一阶段相遇
                ListNode* ptr = head;
                while (ptr != slow) {                 // 第二阶段同步走
                    ptr = ptr->next;
                    slow = slow->next;
                }
                return ptr;
            }
        }
        return nullptr;                                // 无环
    }
};

回顾一下数学：相遇时 slow 走了 a + b 步（a 是头到环口距离，b 是相遇点在环内距环口的距离），fast 走了 2(a + b) = a + b + kL，解得 a = kL − b。从相遇点再走 L − b 就到环口，多绕的 (k−1)L 不改变位置——所以从 head 走 a 步和从相遇点走 kL − b 步同时到达环入口。

踩坑提示：

第一，第二阶段 slow 不能复位回 head，只能保持在相遇点。一个常见笔误是"两个都回 head"，那当然永远相遇在 head。

第二，链表无环时第二阶段循环根本不进。模板里 while fast and fast.next 在无环时会自然退出到 return None，不会污染到第二阶段。

第三，链表头本身就是环入口的情况（比如 1 → 2 → 1 → 2 → ...，环口就是 head）。此时第一阶段相遇时 slow 可能就在 head 或离 head 一圈的位置——第二阶段 ptr = head、while ptr is not slow 直接退出（如果 slow 已经在 head）或同步走一圈追上。两种情况都正确。

复杂度：时间 O(n)（第一阶段最多 a + L，第二阶段最多 a，合计 O(n)），空间 O(1)。

Follow-up：环相关问题就讲到这。如果链表是普通的（没环），但我们想用快慢指针找它的中点呢？

4.3 LC 876 链表的中间节点

链接：LeetCode 876

题意：给一个单链表的头节点 head，返回链表的中间节点。如果有两个中间节点（链表长度为偶数），返回后半部分的第一个节点。

数据范围：

链表节点数：1 到 100
节点值：1 到 100

示例：

输入：head = [1, 2, 3, 4, 5]
输出：节点 3
解释：链表长 5（奇数），中点是下标 2。

输入：head = [1, 2, 3, 4, 5, 6]
输出：节点 4
解释：链表长 6（偶数），两个中间节点是 3 和 4，按题意返回后者 4。

直觉解：先扫一遍数出长度 n，再扫一遍走 n/2 步。O(n) 时间，但要遍历两遍。

更优雅的是一次遍历用快慢指针：fast 走两倍速，fast 到末尾时 slow 恰好在中点。

class Solution:
    def middleNode(self, head: 'ListNode') -> 'ListNode':
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

public ListNode middleNode(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode *slow = head, *fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

为什么循环退出时 slow 在后半段的第一个节点？

链表长 n，slow 走了 k 步时位于下标 k，fast 走了 2k 步时位于下标 2k（如果存在）。
循环退出条件是 fast is null 或 fast.next is null：
- n 是奇数（比如 n = 5），fast 走到下标 4 时 fast.next is null，此时 slow 走了 2 步在下标 2 → 正中间 ✓
- n 是偶数（比如 n = 6），fast 走到下标 6 时 fast is null，此时 slow 走了 3 步在下标 3 → 后半段第一个 ✓

如果题目改成"偶数时返回前半段最后一个"（这是 LC 143 重排链表里需要的），把循环条件改成：

while fast.next and fast.next.next:        # fast 还能走两步才走
    slow = slow.next
    fast = fast.next.next

差别只在循环条件的"边界判定时机"：上面的版本是"fast 还能走再走"，原版本是"fast 已经走完就停"。两个变体后面 §5 会再对比。

复杂度：时间 O(n)，空间 O(1)。比"两次遍历数长度再走一半"更优雅，遍历次数只有一遍。

这三道题共享同一份代码骨架：判环看相遇、找环入口加第二阶段、找中点直接返 slow——区别只在循环退出后做什么。这就是快慢指针这一族题的核心特征。

5. 边界、易错与复杂度

偶数长度链表的中点：取前 vs 取后

这是面试里最容易翻车的点。LC 876 要求取后：[1,2,3,4] 返回 3。但很多变种（LC 143 重排链表、LC 234 回文链表）需要取前，方便切断成"前半段 + 后半段"两个等长子链。

两种写法的区别：

目标	循环条件	偶数 `[1,2,3,4]` 返回
取后中点（LC 876 定义）	`while fast and fast.next`	`3`（下标 2，后半段第一个）
取前中点（用于切链）	`while fast.next and fast.next.next`	`2`（下标 1，前半段最后一个）

记法：while fast and fast.next 是"fast 当前能走两步就走"，会走得更激进，slow 偏后。while fast.next and fast.next.next 是"fast 提前判定，下一步必须能走两步整"，会停得更早，slow 偏前。

奇数长度时两者结果相同（都是正中间）。

空链表与单节点链表

模板 while fast and fast.next 自然处理：

head is null：fast = null，循环不进，slow 还是 null，返回 null（判环 → false / 找入口 → null）。
单节点 head.next is null：fast = head，fast.next is null，循环不进，slow == head。如果 head 自指（自环），需要先比 slow is fast 然后才走——但模板是先走再比，第一轮走完 fast = head.next.next 会 NPE 吗？

回头看：单节点无环 head.next == null，while fast and fast.next 在第 0 轮就退出，没进循环体，没问题。单节点自环 head.next == head，fast.next == head != null，进循环；slow = head.next = head，fast = head.next.next = head，然后 slow is fast 为真，返回 true ✓。

总之模板对所有边界都自洽，不用专门加 if head is None: return False 之类的护栏。

`is` 比较 vs 值比较

判定 slow == fast 时一定要用引用相等（Python 用 is，Java/Go 用 ==，C++ 用 == 比较指针）。如果用 slow.val == fast.val，链表 [1, 1, 1] 没环也会被误判成有环——节点值相等不代表是同一个节点对象。

fast 步长的其他选择

教科书里 Floyd 龟兔默认 fast 走 2 倍速。理论上 fast 走 3 倍、4 倍速也能用，但有两个代价：

第一，找环入口的数学要重推。2(a+b) = a+b+kL → a = kL−b 是基于 2 倍速的等式。换 3 倍速会变成 3(a+b) = a+b+kL → 2a + 2b = kL → 2a = kL − 2b，需要从相遇点走 (kL − 2b)/2 步——多了个除 2，要保证除得尽就麻烦。

第二，循环条件变复杂。3 倍速需要 fast and fast.next and fast.next.next，更容易写错。

工程上保留 2 倍速即可。

复杂度速查

操作	时间	空间
LC 141 判环	`O(n)`	`O(1)`
LC 142 找环入口	`O(n)`	`O(1)`
LC 876 找中点	`O(n)`	`O(1)`
哈希集合判环（基线）	`O(n)`	`O(n)`

n 是链表节点数。有环时上界是 a + L，仍 O(n)。

同源应用：链表之外的 Floyd 算法

快慢指针在链表上是"找环 + 找中点"，但 Floyd 算法的本质是在任何 functional graph 上检测环——只要存在一个"每个节点指向唯一下一节点"的映射 f: X → X，就能用快慢指针追踪 x → f(x) → f(f(x)) 这条轨道找出周期。链表只是这套思路的一个特例。

场景	functional graph 形态	例题 / 应用
链表找环	`f(x) = x.next`，节点是真实链表节点	LC 141 / LC 142
数组中找重复数	`f(x) = nums[x]`，节点是下标 0..n	LC 287（重复数像"链表环入口"）
快乐数判定	`f(x) = sumOfDigitsSquared(x)`，节点是任意整数	LC 202
Pollard's ρ 因子分解	`f(x) = (x² + c) mod N`，节点是模 N 剩余类	数论：分解大整数
伪随机数周期检测	`f` 是 LCG / xorshift 等 RNG	加密 / 仿真领域

LC 287 是这套思路在面试里最经典的"换皮题"——给定 nums[0..n]，其中 nums 元素都在 [1, n]，必有重复——把数组当链表 f(i) = nums[i] 跑 Floyd，环入口就是重复数。O(n) 时间 O(1) 空间。§6.4 给完整代码。

Pro 会员

解锁完整北美 OA 题库

165 家公司 / 1000+ 道真题 · Python · Java · C++ 三语题解 · 月度更新

开通会员已是会员，去登录

7. 小结

快慢指针的核心是"两个游标按不同速度走，靠相对位置或相对速度提取信息"——判环看相遇、找环入口加第二阶段、找中点直接返 slow。空间永远是 O(1)，时间 O(n)。这套思路把"链表是否有环 / 环入口在哪 / 中点是谁 / 倒数第 n 个是谁"这一族问题从 O(n) 空间降到 O(1)。

下一节会把"链表 + 双指针"的范围继续扩到反转、合并、k 个一组反转——LC 206 / 21 / 25 一线题集都属于这一族。

对应灵神题单：链表 / 快慢指针 / 前后指针

进一步阅读：灵茶山艾府《链表题单》；LeetCode 链表标签

链表 · 快慢指针

hasCycle: 1 → 2 → 3 → 4 → 5 → (next = node[2])

解锁完整北美 OA 题库

On this page