判断单链表环并找出环起点：Floyd 判圈算法

1290 字

6 分钟

判断单链表环并找出环起点：Floyd 判圈算法

2026-08-10

算法

链表

/

快慢指针

/

Floyd判圈

/

环检测

/

C

/

C++

/

JavaScript

题目描述#

子问题一：判断链表是否包含环#

给定一个单链表的头节点 head，判断链表中是否存在环。如果链表中有某个节点可以通过连续跟踪 next 指针再次到达，则链表中存在环。

1
输入：head = 3→2→0→-4
2
              ↑_______↓
3
输出：true

子问题二：找出环的起点#

在上题基础上，如果存在环，返回环的入口节点。

1
输入：head = 3→2→0→-4
2
              ↑_______↓
3
输出：节点 2
4
解释：环的入口是节点 2

解题思路#

第一阶段：Floyd 判圈（判断有无环）#

使用快慢指针：slow 每次走一步，fast 每次走两步。

如果链表无环：fast 会先到达 null，判定无环
如果链表有环：fast 和 slow 一定会在环中相遇（就像在圆形操场上，快的人总会套圈慢的人）

第二阶段：找出环的入口（数学推导）#

当 fast 和 slow 在环中相遇后：

将 slow 重新指向链表头部
slow 和 fast 以相同的速度（每次一步）前进
两者再次相遇的节点就是环的入口

数学证明#

设：

链表头部到环入口的距离为 a
环入口到第一次相遇点的距离为 b
环的长度为 L，则相遇点到环入口的剩余距离为 c = L - b

第一次相遇时：

slow 走了 a + b 步
fast 走了 a + b + n·L 步（n 为 fast 多绕的圈数）

因为 fast 速度是 slow 的 2 倍：2(a + b) = a + b + n·L → a + b = n·L → a = n·L - b = (n-1)·L + (L - b) = (n-1)·L + c

a = c + (n-1)·L —— 这意味着从链表头部走 a 步到环入口的距离，等于从相遇点走 c 步到环入口（可能多绕几圈）的距离。

所以，让 slow 从头出发，fast 从相遇点出发，两者同速前进，必定在环入口相遇。

代码实现#

1
#include <stdio.h>
2
#include <stdlib.h>
3
#include <stdbool.h>
4

5
typedef struct ListNode {
6
    int val;
7
    struct ListNode *next;
8
} ListNode;
9

10
/* 检测是否有环 */
11
bool hasCycle(ListNode *head) {
12
    ListNode *slow = head;
13
    ListNode *fast = head;
14

15
    while (fast && fast->next) {
16
        slow = slow->next;
17
        fast = fast->next->next;
18
        if (slow == fast) return true; // 快慢指针相遇，有环
19
    }
20
    return false; // fast 到达末尾，无环
21
}
22

23
/* 寻找环的入口节点 */
24
ListNode* detectCycle(ListNode *head) {
25
    ListNode *slow = head;
26
    ListNode *fast = head;
27

28
    // 第一阶段：判断是否有环
29
    while (fast && fast->next) {
30
        slow = slow->next;
31
        fast = fast->next->next;
32
        if (slow == fast) {
33
            // 第二阶段：寻找环的入口
34
            slow = head;
35
            while (slow != fast) {
36
                slow = slow->next;
37
                fast = fast->next;
38
            }
39
            return slow; // 再次相遇点即为环入口
40
        }
41
    }
42
    return NULL; // 无环
43
}

1
struct ListNode {
2
    int val;
3
    ListNode *next;
4
    ListNode(int x) : val(x), next(nullptr) {}
5
};
6

7
class Solution {
8
public:
9
    // 检测是否有环
10
    bool hasCycle(ListNode *head) {
11
        ListNode *slow = head;
12
        ListNode *fast = head;
13

14
        while (fast && fast->next) {
15
            slow = slow->next;
16
            fast = fast->next->next;
17
            if (slow == fast) return true;
18
        }
19
        return false;
20
    }
21

22
    // 寻找环的入口节点
23
    ListNode* detectCycle(ListNode *head) {
24
        ListNode *slow = head;
25
        ListNode *fast = head;
26

27
        // 第一阶段：判断是否有环
28
        while (fast && fast->next) {
29
            slow = slow->next;
30
            fast = fast->next->next;
31
            if (slow == fast) {
32
                // 第二阶段：寻找环的入口
33
                slow = head;
34
                while (slow != fast) {
35
                    slow = slow->next;
36
                    fast = fast->next;
37
                }
38
                return slow;
39
            }
40
        }
41
        return nullptr;
42
    }
43
};

1
class ListNode {
2
    constructor(val) {
3
        this.val = val;
4
        this.next = null;
5
    }
6
}
7

8
// 检测是否有环
9
function hasCycle(head) {
10
    let slow = head;
11
    let fast = head;
12

13
    while (fast && fast.next) {
14
        slow = slow.next;
15
        fast = fast.next.next;
16
        if (slow === fast) return true;
17
    }
18
    return false;
19
}
20

21
// 寻找环的入口节点
22
function detectCycle(head) {
23
    let slow = head;
24
    let fast = head;
25

26
    // 第一阶段：判断是否有环
27
    while (fast && fast.next) {
28
        slow = slow.next;
29
        fast = fast.next.next;
30
        if (slow === fast) {
31
            // 第二阶段：寻找环的入口
32
            slow = head;
33
            while (slow !== fast) {
34
                slow = slow.next;
35
                fast = fast.next;
36
            }
37
            return slow;
38
        }
39
    }
40
    return null;
41
}

图解过程#

第一阶段：判圈#

1
链表：3 → 2 → 0 → -4
2
           ↑__________↓
3

4
Step 1: slow=3, fast=3
5
Step 2: slow=2, fast=0
6
Step 3: slow=0, fast=2   ← fast 绕了一圈，套圈 slow
7
Step 4: slow=-4, fast=-4 ← 在节点 -4 相遇！有环！

第二阶段：找环入口#

1
第一次相遇后：
2
  slow 重置到头部 (3)
3
  fast 留在相遇点 (-4)
4

5
以相同速度前进：
6
Step 1: slow=2, fast=2
7
        ↓       ↓
8
        两者在节点 2 相遇 → 节点 2 就是环的入口！

复杂度分析#

维度	分析
时间复杂度	O(n) — slow 最多走 n 步（从头到入口再到相遇点），两阶段各 O(n)
空间复杂度	O(1) — 只用了两个指针