目录

一、问题描述

二、常见解法

[方法一：快慢指针（Floyd 判圈算法）](#方法一：快慢指针（Floyd 判圈算法）)

方法二：哈希表法（直观但耗空间）

三、进阶问题：如何找到环的起点？

[1. 数学符号定义](#1. 数学符号定义)

[2. 相遇时的关系推导](#2. 相遇时的关系推导)

[3. 原理直观解释](#3. 原理直观解释)

[4. 代码实现](#4. 代码实现)

[5. 例子说明](#5. 例子说明)

[6. 文字图解](#6. 文字图解)

[7. 常见误区](#7. 常见误区)

四、总结对比

五、结语

六：力扣练习题

一、问题描述

给定一个单链表，判断其中是否存在环。

也就是说：某个节点的 next 指针是否指向了前面的节点，导致链表无限循环。

示意图：

复制代码

1 -> 2 -> 3 -> 4 -> 5

^ |

|_________|

上面的链表从节点 5 指向节点 3，因此形成了一个环。

二、常见解法

方法一：快慢指针（Floyd 判圈算法）

定义两个指针：

slow：一次走一步；

fast：一次走两步；

如果链表无环，fast 最终会遇到 nullptr；

如果链表有环，fast 一定会在环中追上 slow（它们会在环内相遇）。

cpp

复制代码

struct ListNode {

int val;

ListNode* next;

ListNode(int x) : val(x), next(nullptr) {}

};

bool hasCycle(ListNode* head) {

if (!head || !head->next) return false;

ListNode* slow = head;

ListNode* fast = head;

while (fast && fast->next) {

slow = slow->next;

fast = fast->next->next;

if (slow == fast)

return true;

}

return false;

}

项目

复杂度

时间复杂度

O(n)

空间复杂度

O(1)

方法二：哈希表法（直观但耗空间）

用哈希表记录访问过的节点指针，如果访问到重复节点说明有环。

cpp

复制代码

#include

bool hasCycle(ListNode* head) {

std::unordered_set visited;

while (head) {

if (visited.count(head))

return true;

visited.insert(head);

head = head->next;

}

return false;

}

项目

复杂度

时间复杂度

O(n)

空间复杂度

O(n)

三、进阶问题：如何找到环的起点？

判断出"有环"之后，很多面试题会进一步问：

如果存在环，如何找到环的入口节点？

这一部分正是 Floyd 判圈算法的精髓。

1. 数学符号定义

假设链表由两部分组成：

复制代码

[非环部分] 长度 = a

[环部分] 长度 = b

假设相遇点距离环入口的距离为 x。

也就是说：

复制代码

head --a--> 入口 --x--> 相遇点 --(b - x)--> 入口

我们设：

slow 每次走 1 步；

fast 每次走 2 步。

2. 相遇时的关系推导

当两者第一次相遇时：

slow 走了 a + x 步；

fast 走了 2(a + x) 步。

由于 fast 比 slow 多绕了若干圈环，因此：

复制代码

2(a + x) - (a + x) = nb -> a + x = nb

化简得：

复制代码

a = nb - x

这意味着什么？

从相遇点出发，走 nb - x 步，就会回到环的入口。

而因为环的长度是 b，所以"绕 n 圈"是等价的。

因此我们也可以说：从相遇点再走 (b - x) 步，就能回到环的入口。

3. 原理直观解释

可以这样理解：

当 slow 与 fast 相遇时，它们都在环中；

如果此时让一个指针从 head 开始走，另一个从 相遇点 开始走；

两者速度相同，每次走一步：

从头出发的指针需要走 a 步到达环入口；

从相遇点出发的指针需要走 b - x 步回到环入口；

由于根据推导公式 (a = nb - x)，它们会在环的起点重合。

4. 代码实现

cpp

复制代码

ListNode* detectCycle(ListNode* head) {

ListNode* slow = head;

ListNode* fast = head;

// 第一步：判断是否有环

while (fast && fast->next) {

slow = slow->next;

fast = fast->next->next;

if (slow == fast) {

// 第二步：有环，寻找环入口

slow = head;

while (slow != fast) {

slow = slow->next;

fast = fast->next;

}

return slow; // 环的入口

}

}

return nullptr; // 无环

}

5. 例子说明

假设链表如下：

复制代码

a = 3（非环长度）

b = 5（环的长度）

链表结构：

复制代码

head(0) → 1 → 2 → 3 → 4 → 5 → 6 → 7 → (回到3)

slow 每次走一步；

fast 每次走两步；

它们第一次相遇在节点 6；

从头走 a=3 步可以到达入口节点 3；

从节点 6 再走 b-x=3 步（6→7→3）也正好到达节点 3。

两者在环入口相遇。

6. 文字图解

下面用 ASCII 示意整个过程：

复制代码

head

↓

[节点1] → [节点2] → [节点3] → [节点4] → [节点5]

↑ ↓

← ← ← ← ← ← ← ← ← ← ←

↑

|------ 非环长度 a ------|

在相遇点：

- slow 在环内

- fast 在环内，快指针比慢指针多走若干圈

当让 slow 回到 head 后，两者再以相同速度前进：

- 一个从外部走进环

- 另一个从环内走向入口

它们在入口节点重合

7. 常见误区

误区

正确理解

"为什么不是直接在相遇点就是环入口？"

相遇点可能在环内任意位置，取决于 a 和 b。

"为啥一定会在入口相遇？"

因为两者速度相同，且它们相对位置差等于 a，环长是周期结构。

"n 可以是几？"

n 是 fast 多绕的圈数，通常为 1，但数学上不影响结论。

四、总结对比

方法

能判断有环

能找入口

时间复杂度

空间复杂度

思想核心

哈希表

✅

✅

O(n)

O(n)

记录访问节点

快慢指针（Floyd）

✅

✅

O(n)

O(1)

相对速度+数学推导

五、结语

Floyd 判圈算法不仅是链表问题的高频面试题，更是一种"数学与编程的完美结合"。

它展示了空间最优解法 如何通过逻辑关系实现"无痕检测"。

理解它的推导过程，比死记硬背更重要------这样在面对复杂数据结构题目时，你能举一反三。

六：力扣练习题

LeetCode 141. Linked List Cycle

力扣 - 环形链表

LeetCode 142. Linked List Cycle II

力扣 - 环形链表II

免责声明

本文内容仅供学习与参考，旨在帮助读者理解相关算法与编程思想。

文中代码、图示及思路均为学习笔记整理，可能存在疏漏或不足之处。

如在实际应用中出现错误或与特定环境不符，请以实际情况、官方文档或权威资料为准。

封面图来源于网络，如有侵权，请联系删除！