目录

• 1. 笔记概览
• 2. 链表的带环问题
  • 2.1 什么是带环链表
  • 2.2 如何判断链表是否带环
  • 2.3 代码实现：环的检测
  • 2.4 证明一：slow走1步、fast走2步一定能相遇
  • 2.5 证明二：slow走1步、fast走3步能否相遇
  • 2.6 进一步证明：永远追不上的条件是否真的存在
  • 2.7 更一般的情况：fast走N步的分析思路
• 3. 求环的入口点
  • 3.1 方法一：公式推导法
  • 3.2 入口点公式的证明
  • 3.3 方法二：转化为链表相交问题
• 4. 复杂链表的复制（深拷贝）
  • 4.1 题意分析：什么是复杂链表
  • 4.2 难点分析：random指针的处理
  • 4.3 暴力方法：O(n²) 的相对位置法
  • 4.4 巧妙方法：O(n) 的原地插入法
    • 4.4.1 第一步：拷贝节点插入原节点后面
    • 4.4.2 第二步：控制拷贝节点的random指针
    • 4.4.3 第三步：将拷贝节点拆下来组成新链表
• 5. 复习要点

---

1. 笔记概览

这章要完成两个重量级题目：

1. 链表的带环问题——经典的快慢指针应用，配合数学证明
2. 复杂链表的复制——链表操作的"试金石"，综合考察增删查改能力

提示： 本节只讲两个题，但这两个题嵌套了很多小问题，都属于有一定难度的题。

---

2. 链表的带环问题

2.1 什么是带环链表

引入

链表的八种基本结构中包含了"循环"这一维度（单向/双向 × 带头/不带头 × 循环/不循环）。带环链表就是链表中某个节点的 next 指针指向了链表中之前的某个节点，形成了一个环。

带环的三种形态

形态	描述	示意
标准循环链表	尾节点的 next 指向头节点	1→2→3→4→1（回到头）
一般带环	尾节点的 next 指向链表中任意一个中间节点	1→2→3→4→5→3（回到中间）
极端情况	节点的 next 指向自己	1→1（自己指自己）

注意： 带环链表中，尾节点的 next 不一定指向头节点，它可以指向链表中的任意一个节点。很多同学一提到带环就只想到标准循环链表，这是不全面的。

2.2 如何判断链表是否带环

常见错误思路

很多同学会想到以下方法，但这些方法都不可行：

错误思路	为什么不行
判断某个节点的 next 是否等于自己	只有"自环"才能这样检测，一般带环检测不了
用一个指针走，看能否第二次走到自己	你不知道自己进没进环，跟谁比较？
判断是否有 next == NULL	如果带环，next 永远不为空，你会死循环，永远走不出来
判断 next 是否等于 head	head 不一定在环内
加 flag 标记	你不知道什么时候进环了

补充说明： 带环链表的前缀（进环前的部分）有可能很长，环外的节点只遍历一遍就过了，只有在环里面才会重复相遇。单指针遍历根本无法判断自己什么时候进环。

正确方案：快慢指针

现阶段唯一可行的方案就是快慢指针（以后学了 map 和 set 还会有其他方案）。

核心思路——追击问题：

• slow 指针一次走 1步
• fast 指针一次走 2步
• 如果不带环：fast 会先走到链表末尾（fast == NULL 或 fast->next == NULL）
• 如果带环：slow 进环后，fast 已经在环里转了一会儿，两者变成追击问题，最终一定会相遇

本节小结

判断链表是否带环的核心方法是快慢指针：slow走1步、fast走2步。不带环时fast到达末尾；带环时两者在环内相遇。关键在于理解"追击问题"。

2.3 代码实现：环的检测

代码非常简单，重点在于后面的证明。

// 环的检测代码模板
bool hasCycle(struct ListNode* head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    
    while (fast && fast->next) {    // fast不为空且fast->next不为空
        slow = slow->next;          // slow走1步
        fast = fast->next->next;    // fast走2步
        
        if (slow == fast) {         // 相遇 → 带环
            return true;
        }
    }
    return false;  // fast走到末尾 → 不带环
}

设计思路：

1. slow 和 fast 都从 head 出发
2. 循环条件检查 fast 和 fast->next（因为 fast 每次走两步，需要保证两步都有效）
3. 不带环时，链表节点个数分奇偶：偶数个时 fast == NULL，奇数个时 fast->next == NULL
4. 带环时，slow == fast 就说明追上了

注意： 这道题的真正重点不在代码，而在于面试官会追问的证明题——“为什么一定会相遇？有没有可能永远追不上？”

2.4 证明一：slow走1步、fast走2步一定能相遇

证明思路

前提：讨论的是带环的情况（不带环直接结束，无需讨论）。

设定：当 slow 刚进环时，假设 fast 和 slow 之间的距离差为 N（N 为正整数）。

追击过程中的距离变化：

每追击一次（slow走1步、fast走2步）：

• slow 前进 1 步 → 距离增加 1
• fast 前进 2 步 → 距离减少 2
• 净效果：距离缩小 1

$$N\to N-1\to N-2\to \cdots \to 2\to 1\to 0$$

结论：整数每次减1，一定会减到0。距离为0就是追上，即相遇。

提示： 这个证明很简单——整数减1一定会减到零，减到零就相遇了。

本节小结

slow走1步、fast走2步时，每追一次距离缩小1，N一定会递减到0。所以一定能相遇，不可能错过。

2.5 证明二：slow走1步、fast走3步能否相遇

距离变化分析

当 slow 走 1 步、fast 走 3 步时：

• slow 前进 1 步 → 距离增加 1
• fast 前进 3 步 → 距离减少 3
• 净效果：距离每次缩小 2

$$N\to N-2\to N-4\to \cdots$$

分情况讨论

情况一：N 是偶数

$$N\to N-2\to \cdots \to 4\to 2\to 0\text{（追上了！）}$$

偶数减2一定能减到0，第一轮就追上。

情况二：N 是奇数

$$N\to N-2\to \cdots \to 5\to 3\to 1$$

距离减到了 1，而不是 0！

距离为1意味着什么？来看：

追击方向 →
        [fast]  [slow]
距离为1: fast在slow后面一个位置

下一步：slow走1步，fast走3步——fast直接越过了slow！

换句话说，距离为1时会"错过"，进入新一轮追击。

错过后的新距离

设环的长度为 C。错过后，fast 超过了 slow，两者的新距离变为 C - 1。

注意： 这里要理解"距离为1变成C-1"的含义——fast刚刚超过slow一个位置，相当于fast需要再绕一大圈才能追上slow，新距离就是环长减1。

继续讨论 C - 1 的奇偶性

C - 1 的奇偶性	结果
偶数	下一轮追上
奇数	又减到1，又错过，又变成 C-1 → 死循环，永远追不上

永远追不上的条件

同时满足以下两个条件时，会永远追不上：

1. N 是奇数（第一轮错过）
2. C 是偶数（即 C-1 是奇数，第二轮又错过，之后死循环）

本节小结

slow走1步、fast走3步时，距离每次缩小2。N为偶数直接追上；N为奇数会错过，之后看C-1的奇偶性。理论上存在"永远追不上"的条件——但这个条件是否真的能成立，需要进一步证明。

2.6 进一步证明：永远追不上的条件是否真的存在

这是整个证明中最精彩的部分——证明 N是奇数且C是偶数 这个条件不可能同时成立。

建立等式

当 slow 进环时：

• 设入环前的距离为 L
• 设环的长度为 C
• slow 走的距离 = L
• fast 走的距离 = L + x·C + (C - N)（走了L到达环入口，在环内转了x圈，又多走了C-N的距离）

由于 fast 速度是 slow 的 3倍：

$$3L=L+x\cdot C+(C-N)$$

化简得：

$$2L=(x+1)\cdot C-N$$

利用等式分析奇偶性

等式左边 $2L$ 一定是偶数（2乘以任何整数都是偶数）。

所以右边 $(x+1)\cdot C-N$ 也一定是偶数。

现在假设"永远追不上"的条件成立，即 N 是奇数，C 是偶数：

• $(x+1)$ 可以是奇数或偶数
• $(x+1)\cdot C$：偶数（C）乘以任何数都是偶数
• 偶数 - 奇数（N）= 奇数

但右边必须是偶数！矛盾！

补充说明： 这是一个高中水平的反证法——只有"奇数减奇数"或"偶数减偶数"才能得到偶数，"偶数减奇数"不可能得到偶数。

最终结论：为什么一定能追上？

回顾 2.5 节的分析，"永远追不上"需要 N是奇数 且 C是偶数 同时成立。现在用上面的等式来检验这个条件能否成立：

假设条件	代入等式 $2L=(x+1)C-N$	结果
C偶数，N奇数	左边 $2L$ = 偶数；右边 = 偶数×(x+1) - 奇数 = 偶数 - 奇数 = 奇数	左右矛盾，不可能存在

等式约束告诉我们：N是奇数时，C一定也是奇数（不可能是偶数）。

反向代回 2.5 节的分析，穷举所有实际可能的情况：

情况	N的奇偶	C的奇偶（受等式约束）	C-1的奇偶	结果
1	偶数	不用管	—	第一轮直接追上
2	奇数	一定是奇数	偶数	第一轮错过，第二轮追上
3	奇数	偶数	奇数	永远追不上 已证明不可能存在

注意： 关键逻辑链是——2.5 节分析出"追不上"需要 N奇+C偶，但 2.6 节的等式证明了 N奇+C偶 在数学上不可能共存。所以情况3被排除了，现实中只有情况1和情况2，而这两种情况都能追上。这就是为什么最终结论是"一定能追上"。

最终结论：slow走1步、fast走3步，也一定能追上。N偶数第一轮追上，N奇数时C一定也是奇数（C-1为偶数），第二轮追上。

本节小结

"永远追不上"需要 N奇数+C偶数 同时成立，但路程等式 $2L=(x+1)C-N$ 左边恒为偶数，代入"C偶数+N奇数"后右边为奇数，矛盾！所以 N奇数时 C 一定也是奇数，C-1 为偶数，第二轮必追上。结论：slow走1步、fast走3步，一定能相遇。

2.7 更一般的情况：fast走N步的分析思路

对于 slow 走 1 步、fast 走 k 步的一般情况，分析思路类似：

• 每次追击距离缩小 (k - 1)
• 关注的是 N 模 (k-1) 的结果

fast步数	每次距离缩小	第一轮直接追上的条件	最终能否一定追上	分析方式
2步	1	一定（距离减1必到0）	一定（已证明）	最简单，无需讨论
3步	2	N为偶数	一定（2.6节已证明）	奇偶性分析 + 反证法
4步	3	N mod 3 == 0	未完整证明，更复杂	讨论N mod 3的三种余数
k步	k-1	N mod (k-1) == 0	未完整证明，更复杂	更复杂的分类讨论

注意： fast=3步经过 2.6 节的完整证明，确认一定能追上。fast=4步及以上，分析方式类似但更复杂，本文未做完整证明，不能直接下"一定能追上"的结论。

提示： 讨论方式与前面类似，只是更复杂一些。速度差越大，需要讨论的情况越多。

本节小结

快慢指针追击的核心在于"速度差"。速度差为1时最简单（一定追上）；速度差为2时需要奇偶性证明（也一定追上）；速度差更大时讨论更复杂，此处未完整展开。实际做题用slow走1步、fast走2步就够了。

---

3. 求环的入口点

3.1 方法一：公式推导法

引入

面试中常见的进阶问题：已知链表带环，找到环的入口节点。

有一个非常简洁的结论：

一个指针从 head 出发，另一个指针从相遇点出发，两者每次都走1步，最终会在入口点相遇。

// 求环入口点的代码模板
struct ListNode* detectCycle(struct ListNode* head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    
    // 第一步：找到相遇点
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            // 第二步：一个从head走，一个从相遇点走
            struct ListNode* meet = slow;
            while (head != meet) {
                head = head->next;
                meet = meet->next;
            }
            return meet;  // 相遇点就是入口
        }
    }
    return NULL;  // 不带环
}

注意： 很多同学在面试中能写出这段代码，但被问到"为什么"时就答不上来了。如果只能背出代码却解释不了原理，面试通常难以通过——面试官最看重的是理解深度而非死记硬背。

3.2 入口点公式的证明

设定变量

|----L----|----N----|
 head    入口点    相遇点
          |              |
          |----C-N-------|
          |              |
          |------C(环长)--|

• L：从 head 到入口点的距离
• N：从入口点到相遇点的距离（沿 next 方向）
• C：环的长度
• C - N：从相遇点到入口点的距离（继续沿 next 方向走）
  

关键分析：slow不可能走超过一圈

注意： 慢指针在环内不可能走超过一圈。原因：fast速度是slow的2倍，slow都走了一整圈了，fast已经走了两圈，不可能在一圈内追不上（每次距离缩小1，环长C步之内一定追上）。

因此：

• slow 走的距离 = $L+N$
• fast 走的距离 = $L+x\cdot C+N$（x ≥ 1，fast在环内至少转了1圈）

推导

fast 速度是 slow 的 2 倍：

$$2(L+N)=L+x\cdot C+N$$

化简：

$$L+N=x\cdot C$$

$$\boxed{L=x\cdot C-N}$$

进一步化简（将 $x\cdot C$ 拆分）：

$$L=(x-1)\cdot C+(C-N)$$

理解这个公式

这个公式说明了什么？

• 左边 L：从 head 走到入口点的距离
• 右边 $(x-1)\cdot C+(C-N)$：
  • $(x-1)\cdot C$：在环内转若干整圈（不管转多少圈，都回到同一个点）
  • $C-N$：从相遇点到入口点的距离

从相遇点出发的指针先在环里转若干圈（回到相遇点），再多走 $C-N$ 步，恰好到达入口点。而从 head 出发的指针走 L 步也到达入口点。两者同时出发、每次走1步，一定会在入口点相遇！

x 的值	从相遇点出发的指针怎么走
x = 1	直接走 C-N 步到入口
x = 2	转1圈 + 走 C-N 步到入口
x = 3	转2圈 + 走 C-N 步到入口
…	…

补充说明： 不管 x 是多少，从相遇点出发的指针都是在环里转圈圈，转到相遇点又回来，再多走一个 C-N，就和 L 相等了。这不是巧合，而是可证明的数学关系。

本节小结

通过相遇时的路程关系推出 $L=(x-1)\cdot C+(C-N)$，这意味着一个指针从head出发、一个从相遇点出发，每次各走1步，一定在入口点相遇。

3.3 方法二：转化为链表相交问题

思路

如果想不到上面的公式推导，还有一个更直观的方法——把带环问题转化为链表相交问题。

操作步骤：

1. 找到相遇点 meet
2. newHead = meet->next（记录相遇点的下一个节点作为新链表头）
3. meet->next = NULL（断开环，将相遇点作为尾节点）
4. 此时原链表变成两条链表：head → ... → meet(NULL) 和 newHead → ... → 入口点
5. 求这两条链表的交点，就是环的入口点！

// 转化为链表相交的思路
// 假设已经找到了相遇点 meet
struct ListNode* newHead = meet->next;
meet->next = NULL;  // 断环

// 调用之前写好的"求两个链表交点"的函数
struct ListNode* entry = getIntersectionNode(head, newHead);

// 如果需要恢复原链表：meet->next = newHead;
return entry;

提示： 这个方法的好处是不需要数学推导，直接复用之前写过的"链表相交"的代码。坏处是证明虽然简单了，但代码写起来反而更长。

注意： 断开环后是否需要恢复原链表？如果题目不检查就不用管，如果检查了就在返回前加一句 meet->next = newHead 恢复即可。

本节小结

找环入口点有两种方法：一是公式推导法（代码简单，证明复杂）；二是转化为链表相交法（思路直观，代码稍长）。核心都是利用快慢指针先找到相遇点。

---

4. 复杂链表的复制（深拷贝）

4.1 题意分析：什么是复杂链表

引入

提示： 这道题不像前面那道对数理思维要求高，但不管是操作上还是思路上都相当有难度。

复杂链表（也叫随机链表）的每个节点包含两个指针：

struct Node {
    int val;
    struct Node* next;    // 指向下一个节点
    struct Node* random;  // 指向链表中任意一个节点，或NULL
};

指针	指向
next	下一个节点（正常链表结构）
random	链表中任意一个节点，也可能是 NULL

深拷贝（Deep Copy）就是：创建一个和原链表完全一样的新链表，新链表中的节点是全新 malloc 出来的，值、next 关系、random 关系都要一模一样。

4.2 难点分析：random指针的处理

拷贝链表本身很简单——遍历原链表，每遇到一个节点就 malloc 一个新节点，依次尾插即可，这是 $O(n)$ 的。

真正的难点是 random 指针的处理。

核心问题：原链表节点A的 random 指向原链表的节点B，那拷贝链表中对应A’的 random 应该指向B’（B的拷贝）。但是A’怎么找到B’在哪？

注意： 不能直接让拷贝节点的 random 指向原链表的节点。拷贝链表和原链表是两个独立的链表，不能交叉引用。

另一个陷阱：能不能按值去找？比如原节点的 random 指向值为7的节点，就去拷贝链表中找值为7的？

不能按值找！因为链表中可能有重复值。如果有两个值为7的节点，按值找分不清是哪个。必须按相对位置来对应。

4.3 暴力方法：O(n²) 的相对位置法

思路：

1. 先正常拷贝链表（只处理 next）
2. 对每个原节点，计算其 random 指向的是第几个节点（相对位置）
3. 在拷贝链表中找到同样位置的节点，设置 random

时间复杂度：$O(n^2)$——对每个节点都要遍历找相对位置。

提示： 实在想不到更优方法时可以用这个写法，能通过基础用例，但严格要求 $O(n)$ 时不适用。

4.4 巧妙方法：O(n) 的原地插入法

这是当前阶段（未学 map/set）最优雅的 O(n) 解法。

核心思想：把拷贝节点插入到原节点的后面，建立原节点和拷贝节点之间的关联关系。

分三步走：

4.4.1 第一步：拷贝节点插入原节点后面

目标：遍历原链表，对每个原节点 malloc 一个拷贝节点，插入到它的后面。

原链表:     7 → 13 → 11 → 7
插入后:     7 → 7' → 13 → 13' → 11 → 11' → 7 → 7' → NULL
            原   拷    原    拷    原    拷   原   拷

关键代码逻辑：

// 拷贝节点插入原节点后面
struct Node* current = head;
while (current != NULL) {
    // malloc一个拷贝节点
    struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
    copy->val = current->val;
    
    // 插入到current后面（注意顺序！）
    copy->next = current->next;     // 先让copy指向下一个原节点
    current->next = copy;           // 再让current指向copy
    
    // current跳到下一个原节点
    current = copy->next;
}

注意： 插入时一定要先改后面的指针（copy->next = current->next），再改前面的（current->next = copy）。否则会丢失后续节点的链接。或者可以先用一个临时变量 next 保存 current->next。

设计思路：为什么要这样插入？因为找到原节点就能找到拷贝节点（就在它后面），这个关联关系是后面处理 random 的关键。

4.4.2 第二步：控制拷贝节点的random指针

这是整道题的精华所在。

原链表插入拷贝后的结构：
7 → 7' → 13 → 13' → 11 → 11' → 7 → 7' → NULL

核心逻辑：

// 设置random指针——整道题的精华
struct Node* current = head;
while (current != NULL) {
    struct Node* copy = current->next;  // 拷贝节点就在原节点后面
    
    if (current->random == NULL) {
        copy->random = NULL;
    } else {
        // 精华一步：
        copy->random = current->random->next;
    }
    
    current = copy->next;  // 跳到下一个原节点
}

为什么 copy->random = current->random->next 就对了？

• current->random 是原节点的 random 指向的原节点
• current->random->next 就是该原节点后面的拷贝节点
• 因为所有拷贝节点都在对应原节点的后面！

举例说明：

原链表中：13的random → 7（第一个）
那么：13'的random 应该 → 7'（第一个7的拷贝）

代码中：current = 13, 
		current->random = 7
        copy = 13', 
        copy->random = current->random->next = 7->next = 7'

重点： 整段代码的精华都由 copy->random = current->random->next 这一步控制。把这一步想明白了，这道题就解决了大半。

4.4.3 第三步：将拷贝节点拆下来组成新链表

目标：把拷贝节点从混合链表中取下来，尾插成一个独立的新链表，同时（可选）恢复原链表。

// 拆分拷贝链表
struct Node* current = head;
struct Node* copyHead = NULL;
struct Node* copyTail = NULL;

while (current != NULL) {
    struct Node* copy = current->next;
    struct Node* next = copy->next;     // 保存下一个原节点
    
    // 尾插到新链表
    if (copyTail == NULL) {
        copyHead = copyTail = copy;     // 第一个节点
    } else {
        copyTail->next = copy;          // 链接到尾部
        copyTail = copy;                // 更新尾指针
    }
    
    // （可选）恢复原链表
    current->next = next;
    
    current = next;  // 跳到下一个原节点
}

if (copyTail) copyTail->next = NULL;    // 尾节点置空
return copyHead;

提示： 是否恢复原链表取决于评测要求——不报错就不用恢复，如果检查了就在返回前加上恢复语句。这里代码中顺手做了恢复。

整体复杂度分析：

步骤	操作	时间复杂度	空间复杂度
第一步	拷贝插入	O(n)	O(1)*
第二步	设置random	O(n)	O(1)
第三步	拆分链表	O(n)	O(1)
总计	—	O(n)	O(1)

*注：新节点的空间不算额外空间，因为题目本身就要求创建这些节点。

注意： 这道题非常考验链表基本功。插入、遍历、删除、尾插全都用到了。这是链表学习的试金石——如果能理解思路并独立写出来，链表部分就已经掌握到位了。

本节小结

复杂链表深拷贝的O(n)解法分三步：①拷贝节点插入原节点后面；②利用"拷贝在原节点后面"的关系设置random（精华：copy->random = current->random->next）；③拆分成独立链表。这是链表综合操作的试金石。

---

5. 复习要点

核心知识点

• 带环链表的概念：尾节点next指向链表中任意节点（不一定是头节点）
• 快慢指针判环：slow走1步、fast走2步，相遇则带环，fast到NULL则不带环
• 追击问题本质：进环后变成追击，关注"距离变化 = 速度差"
• 走2步必追上证明：距离每次减1，整数减1一定到0
• 走3步的分析：距离每次减2，"追不上"需N奇+C偶，但路程等式证明二者不可能共存，所以也一定能追上
• 求环入口点（公式法）：$L=(x-1)\cdot C+(C-N)$，一个从head走、一个从相遇点走，在入口相遇
• 求环入口点（相交法）：断开环，转化为两个链表的相交问题
• 慢指针不超过一圈：fast速度是slow的2倍，一圈内一定追上
• 复杂链表深拷贝：三步法——插入、设random、拆分
• random指针精华：copy->random = current->random->next，利用拷贝在原节点后面的位置关系

重难点与高频考点

1. 判断链表是否带环：考查快慢指针的应用，关键是理解为什么不能用普通遍历
2. 证明快慢指针一定相遇：考查追击问题的数学分析，距离递减到0的论证
3. 不同步长能否相遇：考查奇偶性分析 + 反证法，建立路程等式分析N和C的关系
4. 求环的入口点：考查公式推导 $L=(x-1)C+(C-N)$，理解"一个从head走、一个从相遇点走"的原理
5. 复杂链表的深拷贝：考查链表综合操作能力，重点是O(n)的原地插入法
6. copy->random = cur->random->next 的理解：整道深拷贝题的核心，考查对链表指针关系的理解

易错点提醒

误区	正解
以为尾节点的next指向NULL就不带环	带环时根本不存在"尾节点"，next永远不为空，会死循环
用普通指针遍历判断是否回到head	head不一定在环内，进环前的"前缀"可能很长
认为slow在环内可能走超过一圈	fast速度是slow的2倍，在slow走一圈之内一定追上
深拷贝时让拷贝节点的random直接指向原链表的节点	必须指向拷贝链表中对应的拷贝节点
深拷贝时按值查找random对应节点	可能有重复值，必须按相对位置或利用结构关系查找

知识关联

• 向前关联：带环问题的"方法二"直接复用了上节课的"链表相交"代码；深拷贝题是链表增删查改的综合应用
• 向后关联：学了 map/set 后，判环和深拷贝都有更简单的解法
• 本节内部关联：两道题都是"代码简单，分析/操作复杂"的类型，前者侧重数理证明，后者侧重指针操作

---

结语： 复杂链表的复制这道题，如果能理解思路并独立写出来，链表这一章节的掌握程度就已经达到了很高的水平。