面试题23：链表中环的入口节点

从“相遇点不一定是入口”开始

先预测：链表 1→2→3→4→5，再由5指回3。快指针每次走两步、慢指针每次走一步，它们第一次相遇的节点一定是3吗？不一定。相遇只证明两者进入同一个环并处于同一位置，那个位置可能是4或5；还需要第二阶段寻找链表中环的入口节点。

无环单链表的快指针最终会到空，或停在没有后继的尾节点。有环时，快慢指针进入有限环后，快指针每轮相对慢指针多前进一步；这个每轮净追近量称为相对步差。相对位置只有有限种，差值按环长取模逐格变化，最终必回到0而相遇。这种“快慢指针判断有环”只需常数个指针。

把第一次相等的环内节点称为。它为后续计数提供一个已知在环内的安全起点，却不直接等于。

作者如何安全取得相遇节点

作者先让 slow=head->next；若它为空，单节点无环链表直接失败。再让 fast=slow->next。循环中先比较，再让 slow走一步、fast走一步并在非空时再走一步。只要 fast 或 slow 为空就退出无环。

struct ListNode {
    int value;
    ListNode* next = nullptr;
};
 
ListNode* meetingNode(ListNode* head) {
    if (head == nullptr) return nullptr;
 
    ListNode* slow = head->next;
    if (slow == nullptr) return nullptr;
 
    ListNode* fast = slow->next;
    while (fast != nullptr && slow != nullptr) {
        if (fast == slow) return fast;
 
        slow = slow->next;
        fast = fast->next;
        if (fast != nullptr) {
            fast = fast->next;
        }
    }
    return nullptr;
}

单节点自环时 slow=head、fast=head，第一次比较立即返回该节点；单节点无环时 slow为空并返回。多节点无环时 fast会先触达空。所有 next 解引用都发生在对应指针已确认非空之后。

也可把两指针都从 head 开始，在循环中先移动再比较，并使用 fast 与 fast->next 均非空的条件。这是等价模板，但初始化、比较时机和循环条件必须成套使用；只替换其中一项可能漏掉自环或产生空解引用。

从相遇点绕一圈统计环长

取得相遇节点后，作者把 nodesInLoop 初始化为1，让一个指针沿 next 前进，直到它的下一节点重新是 meeting。每经过一个新环内节点就加1。这个值就是，也就是“统计环中节点数”。

环长为1的自环无需进入循环，初值1就是答案。环长为3的 3→4→5→3 从相遇点出发，无论相遇在3、4还是5，绕一周都恰好访问三个不同位置。因为 meeting 已确认在环内，计数过程不会遇到空。

若错误地从0开始并在回到 meeting 前检查当前位置，很容易把起点漏掉；若以节点值判断回到起点，重复值会提前终止。必须比较节点地址，计数的是物理节点而不是不同数值。

两个头指针相隔一整圈

得到环长 L 后，让 p1 与 p2 都从 head 出发，p1先走L步。随后两者每次各走一步，直到地址相等。这正是“两个指针相隔环长”的固定间隔法。

假设头到入口有 a 条边。同步开始后 p2 走 a 步首次到入口；p1 总共比它多走 L 步。多走一整圈不会改变在环内的位置，因此 p1 也在入口。它们在此第一次相等，返回该节点。

为什么不会在入口前提前相等？p2仍在非环前缀时，每个前缀节点只有来自前一前缀节点的一条到达路径，p1已经领先L步，不可能回到这些只出现一次的节点。第一次可能相等的位置就是p2进入环的入口。

把建立起来后，定位过程与上一题“倒数第k个节点”同构：先制造距离，再同步直到满足终点条件。这里终点不是尾部，而是两个地址相同。

忠实组合三阶段实现

#include <cstddef>
 
ListNode* entryNodeOfLoop(ListNode* head) {
    ListNode* meeting = meetingNode(head);
    if (meeting == nullptr) return nullptr;
 
    std::size_t nodesInLoop = 1;
    ListNode* cursor = meeting;
    while (cursor->next != meeting) {
        cursor = cursor->next;
        ++nodesInLoop;
    }
 
    ListNode* first = head;
    for (std::size_t i = 0; i < nodesInLoop; ++i) {
        first = first->next;
    }
 
    ListNode* second = head;
    while (first != second) {
        first = first->next;
        second = second->next;
    }
    return first;
}

第一阶段若返回空，后两阶段绝不能执行。第二阶段确认 nodesInLoop 至少为1；第三阶段 first 先行过程中不需要空检查，因为已证明存在环，从 head 继续走任意步都不会到空。

时间复杂度 O(n)，其中 n 可理解为进入环前节点数加环中节点数。检测最多走线性步，计数走一圈，定位再走前缀长度；这些线性项相加仍为 O(n)。只保存若干指针和计数，额外空间 O(1)。

与经典“重置到头”方法的关系

常见 Floyd 入口法在相遇后，把一个指针放回 head，另一个留在 meeting，然后都每次走一步；再次相遇处就是入口。其证明使用头到入口距离、入口到相遇点距离与环长的同余关系，不需要显式统计 L。

作者选择先统计 L，再使用固定环长间隔。两者都正确、复杂度相同，但作者方案额外得到环中节点数，也更容易与上一题的间隔双指针联系起来。重构原书内容时不能把经典变体写成作者源码唯一实现。

若产品同时需要入口和环长，作者方案直接交付两个信息；若只需入口，重置头指针法少一次显式计数。工程选择应依据输出契约和团队可证明性，而不是背诵“标准答案”。

环入口、环长与前缀长度还能推出什么

知道入口后，从 head 走到入口可得到非环前缀长度 a；已知环长 L，总共不同节点数为 a+L。不能用普通直到空的遍历计数，因为有环永不结束。

要断开环，可从入口出发走 L-1 步找到环内最后一个节点，再把它的 next 设为空。只有链表确实由当前调用方独占时才能修改；共享结构或并发读者会看到突变。

若要找到两个有环链表是否相交，先分别找入口。入口相同则在入环前或入口处相交；入口不同但沿一个环能走到另一个入口，说明共享同一环但从不同入口进入；否则不相交。这是入口身份比节点值更重要的例子。

所有权与销毁有环链表

普通 DestroyList 通常沿 next 删除到空；对环链会无限循环或重复释放。作者测试对有环结构逐个保存节点指针并手动 delete，而无环结构才调用通用销毁函数。

更稳妥的测试可以使用栈上节点，raw next 只形成非拥有关系；离开作用域时每个对象恰好析构一次。生产拥有型链表通常不允许 unique_ptr 形成环，因为唯一所有权无法闭合；图结构应使用明确的拥有容器与非拥有边。

返回的入口是借用指针，不转移所有权。调用者不得只删除入口，否则前缀仍指向已释放对象，环中其他节点也泄漏。需要修复结构时应先断环，再按容器所有权统一销毁。

并发修改会破坏所有不变量：fast可能访问已释放节点，计数过程中环长可能变化，固定间隔也不再固定。算法要求整个三阶段期间 next 关系不变并受独占锁或外部同步保护。

作者七组测试锁定全部入口位置

Test1 是单节点无环，返回空；Test2 是单节点自环，入口为该节点。它们共同区分 head->next 为空与 head->next 指回自身。

Test3 构造 1→2→3→4→5→3，入口在中部3；Test4 让5指回1，入口就是头；Test5 让5指回自身，入口在尾且环长为1。Test6 是五节点无环，Test7 是空链表。

自动测试应直接比较返回地址：

#include <cassert>
 
void testEntryNode() {
    ListNode n1{1}, n2{2}, n3{3}, n4{4}, n5{5};
 
    assert(entryNodeOfLoop(&n1) == nullptr);
 
    n1.next = &n1;
    assert(entryNodeOfLoop(&n1) == &n1);
 
    n1.next=&n2; n2.next=&n3; n3.next=&n4;
    n4.next=&n5; n5.next=&n3;
    assert(entryNodeOfLoop(&n1) == &n3);
 
    n5.next = &n1;
    assert(entryNodeOfLoop(&n1) == &n1);
 
    n5.next = &n5;
    assert(entryNodeOfLoop(&n1) == &n5);
 
    n5.next = nullptr;
    assert(entryNodeOfLoop(&n1) == nullptr);
    assert(entryNodeOfLoop(nullptr) == nullptr);
}

测试之间必须完整重设所有受影响的 next，避免上一结构残留影响下一断言。随机测试可先生成长度 a 的前缀和长度 L 的环，记录入口地址，再遍历多组 a、L；特别覆盖 a=0、L=1 和很长前缀。

性能测试不应尝试普通打印整个环链。调试输出必须限制步数，或维护已访问地址集合；否则测试日志本身会无限增长，即使入口算法正确。

正确性证明

无环时 fast 每轮前进两步，有限链表上必先遇到空，meetingNode返回空。有环时两指针最终都进入长度L的环；每轮相对位移增加1模L，至多L轮差值归零，返回一个真实环内相遇节点。

从相遇节点沿 next 首次回到自身恰好经过环内每个节点一次，计数得到L。第三阶段 first 比 second 多走L步；当 second 从头走a步到入口，first总路程为a+L，在环上与走a步的位置相同。

入口前二者不可能相等，到入口时必相等，所以返回唯一入口。三阶段分别保证有环、正确环长和正确入口，组合后对全部有限静态单链结构成立。

本章练习

本章回顾

1. 快慢指针判断有环：无环时fast到空，有环时相对位置最终归零。
2. 第一阶段相遇节点只证明在环内，不一定就是入口。
3. 从相遇节点绕一圈可准确统计环中节点数L。
4. 作者让一个头指针先行L步，使两个指针相隔环长。
5. 同步前进时，后指针到入口，前指针多走一整圈也到入口。
6. 作者方案与相遇后重置头指针方案都为O(n)时间、O(1)空间。
7. 比较必须使用节点地址，环结构销毁前要先断环或逐节点管理。
8. 七组官方测试覆盖入口在中、头、尾、自环、无环和空链。

名词解释