环形链表II：从快慢指针数学推导到入环点定位

刷链表题的时候，环形链表II（LeetCode 142）是一道大概率绕不过去的坎。很多朋友在141题"判断链表是否有环"上花十分钟就写完了，结果面试官追加一句"那请你找到环的入口节点"，当场就卡住了。这道题刷完之后，你会发现快慢指针不只是"追及问题"这么简单，它背后藏着一个非常干净的数学等式，理解了这个等式，你才算真正拿下了环形链表这一整类问题。

这篇文章我打算从题目本身出发，把快慢指针法的推导过程掰开揉碎讲清楚，再给出C++和Python两个完整实现，最后聊一聊环形结构在真实工程里到底从哪儿来，以及怎么用快慢指针的思想去排查线上死循环之类的问题。不管你是正在准备算法面试，还是工作中要和链表、循环结构打交道，这篇都能给你点实在的东西。

1. 环形链表II到底比"判断有环"难在哪里

1.1 题目描述和两种输出要求

先明确一下题目本身。给你一个单链表的头节点head，需要你判断这个链表是否存在环，如果存在，返回环的第一个节点（也就是入环点）；如果不存在，返回null。注意，这里不是简单地返回true/false，而是要精确定位到环的入口节点。

这和141题的区别看起来只是"多返回一个节点"，但难度差的不是一点半点。判断有没有环，你只要让快慢指针跑起来，一旦相遇就说明有环，跑完了都没碰上就说明没环，整个过程不需要知道任何位置信息。而环形链表II要求你从相遇的信息里再反推出一个具体位置，这就逼着你必须理解两个指针的路程关系，而不是靠背模板。

题目里还有一个隐含约束：不要修改链表结构。这意味着你不能用"破坏链表"的方式来标记节点，比如遍历过程中把每个访问过的节点next指向某个特殊节点，这种思路在思路上可行，但不符合题目要求，而且面试官看到你打算改链表结构，大概率会直接打断你。

1.2 没学快慢指针之前，你能想到哪些方案

先说断链法。思路很简单：从头遍历，每经过一个节点，就把它的next指针指向前一个节点或者某个标记节点。如果遍历过程中发现某个节点的next已经指向了标记节点，说明它之前被访问过，也就是回到了环上。这个办法能定位入环点，但代价是链表被破坏了，原结构无法恢复，在工程里这种操作基本不可接受，在题库里也过不了。

再说哈希标记法。用一个哈希表记录访问过的节点，遍历链表，每次遇到一个新节点就检查它是否已经出现在哈希表里，如果是，那这个节点就是环的入口。这个办法不破坏链表，思路也直观，空间复杂度是O(n)，在面试里作为保底方案是合格的，但如果说"最优解"，面试官想听的还是快慢指针。

还有一种是"时间戳法"，给每个节点结构体里加一个访问标记字段，本质上和哈希法一样，只是空间的载体不同，而且往往需要改动节点定义，更麻烦。

我当初第一次做这道题的时候，第一反应也是哈希表，毕竟"看到重复就返回"这个直觉太自然了。但后来真正理解了快慢指针的推导，才发现一个有意思的现象：哈希法其实是在用"空间记忆"来代替"数学推理"，而快慢指针是用速度差来构造一个可计算的等式。后者只需要O(1)空间，而且在推导过程中你会对链表结构有更深的理解，这是哈希法给不了的。

1.3 为什么面试官默认"你应该会快慢指针"

说句实在话，如果你去面试，面试官问环形链表II，他心里默认的解法就是快慢指针，因为这是教科书级别的经典方案，也是考察"你懂不懂数学证明"的一个好切口。

你可能会说："哈希表也能做啊，为什么非要快慢指针？"这里有个真实的面试逻辑：哈希表方案考察的是你会不会用基础数据结构，快慢指针方案考察的是你能不能从已知现象（相遇）推导未知信息（入口位置）。后者显然更能区分候选人的算法功底，这也是为什么几乎所有题解都会重点讲快慢指针。

但我要多说一句：如果你在面试现场实在想不起来快慢指针怎么证明，先把哈希表方案写出来，保证能跑通、能讲清楚，然后再补一句"我知道还有空间O(1)的快慢指针做法，给我一点时间我可以推出来"。大多数面试官会给你这个时间，因为这不是在考背诵，是在考你有没有逻辑推导能力。

2. 快慢指针法：两次"相遇"背后的距离恒等式

2.1 规则先摆清楚

快慢指针的规则很简单：慢指针slow每次走1步，快指针fast每次走2步，两个指针都从head出发。如果链表里存在环，那么fast一定会"追上"slow，也就是在某一个节点上两个指针相等。如果链表没有环，fast会先走到链表末尾的空指针，循环结束，返回null。

这里有一个需要想明白的点：fast为什么一定会追上slow？如果链表有环，当slow进入环之后，fast已经在环里绕圈了，由于fast的速度是slow的两倍，两者的相对速度是1步/次，等价于slow不动、fast以每轮1步的速度靠近它，所以只要跑道足够长（环的长度有限），fast必然会在某一点经过slow的位置。

很多人在这一步会犯一个直觉错误：觉得fast速度太快，可能会"跳过"slow。但因为在环上每经过一轮，fast和slow之间的距离只减少1（相当于slow不动，fast一次靠近1步），所以不存在跳过的问题。如果fast一次走3步、slow一次走1步，反而可能出现跳过的风险，这也是为什么经典的快慢指针用2倍速而不是3倍速的原因之一。

2.2 第一次相遇：梳理两个指针的路程关系

设链表中非环部分的长度为a（从head到入环点，不含入环点，或者说入环点之前的节点数），从入环点到第一次相遇点的长度为b（沿着链表方向走），整个环的长度为c。

当慢指针slow到达入环点时，它走了a步。此时fast因为速度是slow的两倍，已经走了2a步，大概率已经在环里绕了若干圈了。两个指针继续走，直到第一次相遇。

相遇时，假设slow从入环点进入后又走了b步才与fast碰面，那么slow的总路程是：

s = a + b

fast呢？它走到相遇点的时候，除了走完a + b这段外，还在环里多绕了n整圈（n≥1），所以fast的总路程是：

f = a + b + n * c

由于fast的速度是slow的2倍，相同时间内fast的路程是slow的2倍：

2s = f

代入上面两个式子：

2(a + b) = a + b + n * c

化简得到：

a + b = n * c

也就是说：

a = n * c - b

这个等式就是整个题目的核心。它告诉你两件事：第一，slow在第一次相遇时，走的步数a+b正好是环长c的整数倍；第二，从链表头到入环点的距离a，等于"n圈环长减去入环点到相遇点的距离b"。

2.3 第二次"相遇"：从头走到入口的是谁

有了a = n * c - b这个等式，定位入环点就很简单了。

现在，我们把一个指针（假设叫ptr）放回链表头head，另一个指针（就是留在相遇点的slow）保持原地不动。然后让这两个指针都以"每轮1步"的速度往前走。

ptr从head出发，走a步，正好到达入环点。

slow从相遇点出发，也走a步。因为slow已经在环内，它走的a步对应环上的长度a。而前面已经推出a = n * c - b，也就是说，slow从相遇点出发，沿着链表方向走n * c - b步，相当于先走了n圈回到了相遇点，再往回退b步。往回退b步，正好是从相遇点退到入环点（因为相遇点就是从入环点出发走b步到达的，反过来走c-b步也能到，但更直接的理解是：a + b = n * c，所以从相遇点走a步，等价于从入环点走a + b步，即n * c步，正好回到入环点）。

换个说法：slow从相遇点出发走a步，到达的位置就是入环点。

所以当ptr和slow分别从两头发力，各自都走a步之后，它们必然在入环点相遇。这时候返回ptr（或者slow）就是答案。

如果你觉得这一步有点绕，我换一个生活化的类比。想象一个环形操场上的两个人，A从操场外的某条直线跑道起点出发，跑到操场入口用了a秒；B一开始就在操场里绕圈，某一刻他在操场上的一个位置。现在你知道B从这个位置再跑a秒，正好回到操场入口，那么让A从直线跑道起点出发、B从当前位置出发，各自都以"每秒一步"的速度跑，他们就会在操场入口碰面。原因不是他们互相追逐，而是他们俩刚好有一条长度相等的路都要走，这条路恰好都通向操场入口。

2.4 一个非常容易踩的误区：第二次不是让slow回到head

我见过很多人在理解这个解法时，会写成"让slow回到head，然后快慢指针各走一步，相遇即为入口"。这个写法的方向反了。

正确的做法是：两个指针中只有一个回head，另一个留在第一次相遇点。然后两个都以1倍速往前走，再次相遇的地方才是入环点。

为什么不能两个都回head然后再跑一次？因为两个都回head、同速跑，是永远追不上的，它们会一直保持一个在前一个在后。第二次相遇的关键是利用"相遇点位置"和"头部位置"到入环点的距离相等这个性质，而不是重新追逐。

我一开始也在这个地方绕了一阵子，后来干脆拿笔用纸画了一个带环的链表，把a、b、c先标成具体数字，比如a=3，b=2，c=5，然后一步一步模拟两个指针的走动，才彻底搞明白。这种题真的建议亲手模拟一遍，比看任何讲解都有用。

3. 完整代码实现与细节陷阱

3.1 C++版本：从结构体定义到完整函数

先看C++写法。链表节点定义一般是这样的：

cpp复制struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

然后是完整函数：

cpp复制class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head;
        ListNode *fast = head;

        // 第一次循环：寻找相遇点
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                break; // 相遇，退出循环
            }
        }

        // 如果没有环，fast一定先走到空指针
        if (!fast || !fast->next) {
            return nullptr;
        }

        // 第二次循环：一个从头开始，另一个从相遇点开始
        ListNode *ptr = head;
        while (ptr != slow) {
            ptr = ptr->next;
            slow = slow->next;
        }
        return ptr;
    }
};

这里面有几个细节我要专门说一下。

第一个是while条件为什么是fast && fast->next。因为每次循环里fast要往前跳两步，也就是fast = fast->next->next，这要求fast本身不为空，而且fast->next也不为空，否则访问fast->next->next就会解引用空指针，直接段错误。这个判断的顺序绝对不能写反，先判断fast，再利用短路求值去判断fast->next。

第二个细节是break和if判断的组合。找到相遇点之后立即break，循环结束后还要再判断一次!fast || !fast->next，用来区分"因为相遇而退出"和"因为走到链表末尾而退出"两种情况。如果是因为末尾退出，说明链表无环，直接返回nullptr。

第三个细节是第二次循环里，我新建了一个ptr指向head，slow留在相遇点。这里不要再动fast了，它会误导你。很多新手会把第一次循环里的fast也拿来做第二次循环的起点，最后得到错误结果。

3.2 Python版本：引用比较要注意

Python版本的链表节点定义和LeetCode一致：

python复制class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

函数实现：

python复制class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        slow = head
        fast = head
        
        # 第一次循环：寻找相遇点
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                break
        
        # 无环判断
        if not fast or not fast.next:
            return None
        
        # 第二次循环：共同走向入环点
        ptr = head
        while ptr is not slow:
            ptr = ptr.next
            slow = slow.next
        
        return ptr

Python有一个和C++不太一样的地方：判断两个节点是否相同，要用is而不是==。is比较的是对象的身份标识（内存地址），==比较的是值。如果链表里两个节点的val恰好相等，用==判断会出现"值相同但不是同一个节点"的情况，这是环形链表相关题目里非常隐蔽的一个坑。

我见过有人写if slow == fast:，在小数据量的测试用例里碰巧没出问题，因为值碰巧都不同或者重复值没有出现在关键路径上。但只要链表里有重复值，这个判断就可能把两个不同节点误判为同一个，导致程序行为完全错误。所以，判断节点身份，一律用is。

另外，Python代码里while循环结束后的那句if not fast or not fast.next:也要保留，别想着用else代替。有些写法把相遇判断放在while内部然后直接return，外部再统一处理无环情况，也行，但我个人觉得上面这种"break + 事后判断"的结构更清晰，逻辑分支一目了然。

3.3 边界条件：这几个用例必须测

写代码不是能跑就完了，边界条件才是拉开差距的地方。环形链表II至少应该手动测下面几种情况：

我建议你在本地调试这些例子，特别是入环点在头节点的情况。这种场景下，第一次循环里slow和fast从同一个节点出发，直接就在head相遇了，第二次循环ptr=head、slow也在head，循环一次都不执行，直接返回head，逻辑上没问题，但如果你在代码里不小心把slow初始化为head->next，这种场景就过不去。

还有那个"单节点自环"的用例，fast && fast->next当fast不为空且fast->next指向自己时成立，slow和fast第一次移动后都指向那个节点，相遇，一切正常。但如果你的while条件写成了fast->next && fast->next->next，单节点自环反而能过，双节点成环又可能出问题，所以用fast && fast->next最稳妥。

3.4 提交后最常碰到的两类报错

第一类是超时（Time Limit Exceeded）。出现这个，十有八九是while条件写错了，导致fast永远走不到链表末尾。常见写法错误包括：把fast && fast->next写成fast->next && fast->next->next，或者忘记更新fast。如果你在本地测试小链表没问题，但大链表超时，优先检查快指针的更新语句。

第二类是死循环。这个常见于你已经找到相遇点但忘记break，或者第二次循环里两个指针的步长不一致，导致它们永远追不上。记住一个原则：第一次循环里快慢指针步长是2:1，第二次循环里两个指针步长必须是1:1，如果写成1:2，它们可能刚好错过，又因为都在环上，会一直追下去。

4. 哈希表方案：空间换时间的另一条路

4.1 哈希表的实现思路

快慢指针是空间O(1)的最优解，但哈希表方案也有它的价值，至少它能让你在没有数学推导的情况下拿到一个正确答案，而且在某些工程场景里，哈希表方案反而更直观、更不容易出错。

思路非常简单：遍历链表，把每个访问过的节点引用存进一个set（集合），在访问新节点之前，先检查这个节点是否已经在集合里了。如果在，说明又回到了一个之前经过的节点，那这个节点就是入环点。

python复制class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        visited = set()
        cur = head
        while cur:
            if cur in visited:
                return cur
            visited.add(cur)
            cur = cur.next
        return None

注意这里存的是节点对象的引用，不是节点的值。原因还是同一个：链表中可能出现多个节点的val相同，用值去重会把不同的节点混在一起。

4.2 两种方案的真实对比

把两种方案放在一张表里看差异：

时间复杂度两者相同，都是O(n)，这里的n是链表长度，就算有环，快慢指针也最多走不到两圈就能相遇，整体还是线性。空间复杂度就差在哈希表的set上。

在实际工程里，如果你只是在调试时临时判断一个链表有没有环、入口在哪，哈希表方案完全够用，写起来也快。但如果你是在一个对内存敏感的环境里（比如嵌入式设备、内核态代码），哈希表方案的O(n)额外空间可能就有点奢侈了，这时候快慢指针的O(1)空间优势就很明显。

4.3 面试的时候怎么选

我个人的建议是：如果面试官没有明确要求最优解，你先把哈希表方案讲清楚、写完整，这能证明你的基本功。写完之后主动提一句"这个解法空间复杂度是O(n)，我还能用快慢指针做到O(1)空间"，然后趁热打铁把推导过程讲一遍，再写出快慢指针版本。

这种做法比上来就直接写快慢指针更稳妥，因为哈希表方案基本不会写错，能给你一个"保底分"，而快慢指针是你的"加分项"。反过来，如果你一开始就写快慢指针但证明过程卡壳了，面试官可能会觉得你只是背了代码，反而扣分。

当然，如果你对快慢指针的推导已经烂熟于心，直接上最优解也没问题。我自己现在写这道题基本不会再用哈希表了，但面试的时候还是会先说一句"有两种方案，我先讲空间O(1)的"。

5. 环形链表在工程里的真实来处与排查经验

5.1 代码里为什么会出现"环"

很多人刷完这道题觉得它只是面试题，跟实际工作没什么关系，其实不是。环形结构在真实代码里一点不少见，只是它出现的时候往往是bug，而且是很难排查的那种。

最常见的来源是双向链表。比如你实现一个LRU缓存，用双向链表维护访问顺序，头尾指针互相链接。如果代码里在插入或删除节点时有一处指针赋值错了，比如应该把prev指向新节点结果指向了下一个节点，链表就可能出现一个意外的环。表现出来就是遍历缓存列表的时候永远走不完，程序卡死。

第二种常见来源是对象图遍历。做配置解析、依赖注入、序列化的时候，如果对象之间存在循环引用（A里面引用了B，B里面又引用了A），在没有设置深度限制的情况下，递归遍历会无限循环下去。这种问题和链表成环本质上是同一类问题。

第三种是嵌入式或操作系统中的内存管理。有些内存池会维护一个空闲块链表，分配和释放时不断把块移进移出。如果链表链接关系因为越界写入被破坏，也有可能形成环，导致分配器陷入死循环，系统直接hang住。

5.2 用快慢指针思想排查问题的一次实际经历

我以前遇到过一个问题：一个后台任务在处理一批配置对象时，某个处理函数突然不返回了，日志停在同一个对象ID上反复刷。第一反应是"可能配置里有循环引用"，因为配置对象之间允许互相引用，处理逻辑会顺着引用关系一路遍历下去。

当时那个配置结构本质上是一张有向图，不是单链表，但排查思路和快慢指针是一样的。我写了一个临时脚本，把对象引用关系抽象成"每个对象只保留一个'下一个'指针"的形式，然后用快慢两个游标去遍历，跑一会儿就发现两个游标在某一批对象上相遇了，说明这里的引用链路确实成环了。

找到环之后，我再顺着引用关系把环上的具体对象打出来，很快就定位到是配置里一个字段错误地指向了它的上级节点，形成了A->B->C->A的闭环。修复之后，顺手在遍历代码里加了一个"最大访问次数"的保护，当访问次数超过对象总数时就报错退出，防止以后再出现类似问题时把整个进程拖死。

这件事给我的体会是，快慢指针不是一个只活在LeetCode里的技巧，它实际上是一个"在有限空间里检测循环"的通用思想。你不需要知道环在哪里，也不需要记录所有访问过的位置，只要两个不同速度的游标能相遇，就能证明这里有环。这种能力在很多无法使用哈希表的场景里特别值钱。

5.3 平时写代码时防止意外成环的几个习惯

思路决定出路，习惯决定bug率。我从那以后写遍历代码时，基本会坚持下面几个习惯。

第一，凡是遍历一个可能包含循环引用的结构，都设置一个最大迭代次数上限。这个上限不需要很精确，估算一个业务上不可能超过的数字就行，比如"最大处理100万个节点，超过就报错"。一旦真的出现环，程序不会无限卡死，而是会带着错误信息快速失败，排查起来会容易得多。

第二，在链表插入、删除的函数里，宁可多写几行临时指针，也不要为了省变量而直接交换next指针。很多环的源头都是"我以为这一步改的是next，实际上改到了prev"这样的低级错误。

第三，做结构设计的时候提前想清楚：这个结构允不允许成环？如果允许，遍历时就要做判重；如果不允许，就应该在插入时断言"新节点的next不能指向已经在链表中存在的节点"，从源头拦截。

这三条习惯配合起来，大部分环的问题都能提前被发现，就算真漏到线上，也能靠排查思路快速定位，不至于通宵达旦抓瞎。

回到环形链表II这道题本身，它让我最受益的不是背下了快慢指针这个模板，而是逼着我亲手推了一遍a+b=nc这个等式。推完之后再去看其他"找链表中点""删除倒数第N个节点"这类快慢指针变种题，你会突然有一种融会贯通的感觉，因为你已经理解了两个指针之间的路程关系，而不是单纯记住"一个走两步一个走一步"。

最后分享一个我自己的小习惯：刷这类推导型题目时，我会在纸上把a、b、c换成具体数字跑一遍完整流程，比如a=3、b=2、c=5，然后手动模拟slow和fast每一轮的位置变化，直到自己在纸上能写出每一步的坐标。这个习惯做完之后，代码里那些边界条件基本就不会再出错了，也推荐你试试。