doocs/leetcode 题解精讲：面试题 02.08 环路检测（快慢指针求链表环入口）

导读

本文围绕《程序员面试金典（第 6 版）》面试题 02.08「环路检测」（Linked List Cycle LCCI）展开，给出从题目定义、示例到两种解法的完整分析：先介绍借助哈希表记录已访节点的朴素做法，再深入推导快慢指针（Floyd 判圈）如何在 $O(1)$ 额外空间内定位环的入口节点。读完本文，你将掌握「判断链表是否有环」与「求环入口节点」两件核心技能，并可直接对照仓库中 Python、Java、C++、Go、TypeScript、JavaScript、Swift 七种语言的源码实现。本题在仓库中收录于 lcci/02.08.Linked List Cycle，难度中等，标签为「链表」。

题目理解

给定一个有环链表，实现一个算法返回环路的开头节点。 有环链表的定义：在链表中某个节点的 next 元素指向在它前面出现过的节点，则表明该链表存在环路。

题目的输入用两个参数描述链表：head 表示链表的节点值数组，pos 表示尾节点 next 指针所指向节点的下标（pos = -1 表示无环）。注意这里 pos 仅用于测试用例的构造说明，真正的算法输入只有链表的头节点指针，返回值是环入口节点（无环时返回 null/nil）。

原文档给出了三个示例：

示例	输入	输出	解释
示例 1	head = [3,2,0,-4], pos = 1	tail connects to node index 1	链表中有一个环，尾部连接到第二个节点
示例 2	head = [1,2], pos = 0	tail connects to node index 0	链表中有一个环，尾部连接到第一个节点
示例 3	head = [1], pos = -1	no cycle	链表中没有环

进阶要求：是否可以不用额外空间解决此题？这正是快慢指针解法存在的意义——将空间复杂度从 $O(n)$ 降到 $O(1)$。

方法一：哈希表记录已访节点

最直观的思路是：从 head 开始遍历链表，用哈希表（或集合）记录每一个已经访问过的节点；当遇到第一个重复出现的节点时，它必然是环的入口。

该方法思想简单、正确性显而易见，但需要 $O(n)$ 的额外空间存储访问记录，不满足题目的进阶要求，因此仅作为对比方案。接下来重点讲解空间 $O(1)$ 的快慢指针法。

方法二：快慢指针（Floyd 判圈）求环入口

算法流程

1. 判环：令 fast 每次走 2 步、slow 每次走 1 步，同时从 head 出发。若链表无环，fast 会先到达链表尾部（fast 或 fast.next 为空），直接返回 null。
2. 定位入口：若快慢指针相遇，说明链表有环，且相遇节点一定在环中。此时让一个答案指针 ans 指向 head，让 ans 与 slow 同时每次走 1 步，二者相遇的节点即为环的入口节点。

为什么相遇后从头再走一步就能找到环入口？

不妨假设：

• $x$：链表头节点到环入口的距离；
• $y$：环入口到快慢指针相遇节点的距离；
• $z$：相遇节点到环入口的距离；
• $k$：相遇时快指针在环中绕的圈数。

则慢指针走过的距离为 $x + y$，快指针走过的距离为 $x + y + k \times (y + z)$。由于快指针速度是慢指针的 2 倍，有：

$$2 \times (x + y) = x + y + k \times (y + z)$$

化简得：

$$x + y = k \times (y + z)$$

$$x = (k - 1) \times (y + z) + z$$

也就是说：从链表头部走到环入口的距离 $x$，恰好等于「相遇节点出发，绕环 $(k-1)$ 圈后再走 $z$」的距离。因此让 ans 从头部、slow 从相遇节点同速前进，它们必然在环入口相遇。

下图是仓库中的环路结构示意图，直观标注了头节点、环入口、快慢指针相遇节点以及 $x$、$y$、$z$ 三个距离变量：


复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是链表中节点的数目。判环阶段快慢指针至多遍历整个链表，定位阶段两个指针同速前进的步数不超过链表长度。
• 空间复杂度：$O(1)$，仅使用 fast、slow、ans 三个指针变量，不使用额外数据结构。

多语言实现

仓库在 lcci/02.08.Linked List Cycle 目录下为本题提供了七种语言的独立源码文件（Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.js、Solution.swift），与 README 中的代码块一一对应。以下实现均采用快慢指针法，可直接复制运行。

Python3

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast = slow = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                ans = head
                while ans != slow:
                    ans = ans.next
                    slow = slow.next
                return ans

对应源码：Solution.py

Java

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                ListNode ans = head;
                while (ans != slow) {
                    ans = ans.next;
                    slow = slow.next;
                }
                return ans;
            }
        }
        return null;
    }
}

对应源码：Solution.java

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                ListNode* ans = head;
                while (ans != slow) {
                    ans = ans->next;
                    slow = slow->next;
                }
                return ans;
            }
        }
        return nullptr;
    }
};

对应源码：Solution.cpp

Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
	fast, slow := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			ans := head
			for ans != slow {
				ans = ans.Next
				slow = slow.Next
			}
			return ans
		}
	}
	return nil
}

对应源码：Solution.go

TypeScript

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function detectCycle(head: ListNode | null): ListNode | null {
    let [slow, fast] = [head, head];
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) {
            let ans = head;
            while (ans !== slow) {
                ans = ans.next;
                slow = slow.next;
            }
            return ans;
        }
    }
    return null;
}

对应源码：Solution.ts

JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
    let [slow, fast] = [head, head];
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) {
            let ans = head;
            while (ans !== slow) {
                ans = ans.next;
                slow = slow.next;
            }
            return ans;
        }
    }
    return null;
};

对应源码：Solution.js

Swift

/*
* public class ListNode {
*    var val: Int
*    var next: ListNode?
*    init(_ x: Int) {
*        self.val = x
*        self.next = nil
*    }
* }
*/

class Solution {
    func detectCycle(_ head: ListNode?) -> ListNode? {
        var slow = head
        var fast = head

        while fast != nil && fast?.next != nil {
            slow = slow?.next
            fast = fast?.next?.next
            if slow === fast {
                var ans = head
                while ans !== slow {
                    ans = ans?.next
                    slow = slow?.next
                }
                return ans
            }
        }
        return nil
    }
}

对应源码：Solution.swift

实现细节与易错点

1. 循环终止条件：所有实现都使用 fast != null && fast.next != null（Python 中为 fast and fast.next）作为循环条件。这既保证了 fast.next.next 不会空指针解引用，也天然覆盖了「无环」情形——此时 fast 或 fast.next 必先为空，循环正常结束并返回 null/nil/None。
2. 判空与单节点：head 为空或只有一个节点且无环时，循环条件立即不成立，直接返回空值，无需特判。
3. 相遇判断：链表节点是引用类型，slow == fast（Swift/Java 中用 ===/==，Go/TS 中用 ==/===）比较的是节点引用是否相同，而不是节点值——环上可能出现值相同的不同节点，必须比较指针/引用。
4. 第二步的起点：相遇后 ans 必须从 head（而不是从 slow 或 fast）重新出发，与 slow 同速推进，这是数学推导 $x = (k - 1)(y + z) + z$ 的直接落点。

相关资源

• 题目在仓库中的完整目录：lcci/02.08.Linked List Cycle，含中英文题解（README.md、README_EN.md）与全部语言源码；
• 环路示意图：images/linked-list-cycle-ii.png；
• 本题目录索引见 lcci/README.md，该文件完整列出了《程序员面试金典》全部题解；更全面的链表与双指针题型，可继续浏览仓库 solution 目录下的 LeetCode 题解系列。