企业官网建设流程全解析

单链表算法题（四）：高级应用篇

前言

前三篇我们分别学习了：

• 基础操作：移除元素、反转链表、找中点、合并链表
• 进阶技巧：链表分割、回文判断、相交链表
• 环与数学：环形链表的判断与证明

本篇作为系列的最后一篇，将讲解链表题目中最具挑战性的一道题——随机链表的复制。

这道题被称为"链表界的深拷贝"，它综合了插入节点、指针操作、链表分离等多种技巧，是检验链表掌握程度的试金石。

终极题目：随机链表的复制

LeetCode 138. 随机链表的复制

给你一个长度为n的链表，每个节点包含一个额外增加的随机指针random，该指针可以指向链表中的任何节点或空节点。

构造这个链表的深拷贝。深拷贝应该正好由n个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的next指针和random指针也都应指向复制链表中的新节点。

示例

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]] 解释： 节点0: val=7, random=null 节点1: val=13, random=节点0 节点2: val=11, random=节点4 节点3: val=10, random=节点2 节点4: val=1, random=节点0

节点定义

structNode{intval;structNode*next;structNode*random;};

思路分析

这道题的难点在于random指针。

如果只有next指针，我们只需遍历原链表，逐个创建新节点并连接即可：

// 只有 next 指针的简单复制structNode*copyList(structNode*head){structNode*dummy=malloc(sizeof(structNode));structNode*tail=dummy;structNode*cur=head;while(cur!=NULL){structNode*copy=malloc(sizeof(structNode));copy->val=cur->val;tail->next=copy;tail=copy;cur=cur->next;}returndummy->next;}

但有了random指针，问题就复杂了：

复制节点时，它的random指向的是原链表的节点，但我们需要它指向复制链表中对应的节点。

怎么建立"原节点 → 复制节点"的映射关系呢？

三种解法对比

哈希表法简单直观，但需要额外空间。三步法更巧妙，空间复杂度 O(1)，是面试官更欣赏的解法。

解法一：哈希表法（直观易懂）

核心思路：

1. 第一遍遍历：创建所有新节点，用哈希表记录原节点 → 复制节点的映射
2. 第二遍遍历：设置每个复制节点的next和random

structNode*copyRandomList(structNode*head){if(head==NULL){returnNULL;}// 哈希表：原节点 → 复制节点// 在 C 语言中，我们可以用数组或自己实现哈希表// 这里为了演示，使用一个简单的映射数组（假设节点地址范围有限）// 实际面试中，C++ 可以用 unordered_map，C 需要自己实现// 由于 C 没有内置哈希表，这里展示核心逻辑// 实际代码请参考下面的"三步法"，它是 O(1) 空间的returnNULL;}

由于 C 语言没有内置哈希表，实际面试中如果使用 C 语言，更推荐三步法。如果用 C++/Java/Python，哈希表法也很常用。

C++ 版本（供参考）：

classSolution{public:Node*copyRandomList(Node*head){if(!head)returnNULL;unordered_map<Node*,Node*>map;Node*cur=head;// 第一遍：创建所有节点while(cur){map[cur]=newNode(cur->val);cur=cur->next;}// 第二遍：设置 next 和 randomcur=head;while(cur){map[cur]->next=map[cur->next];map[cur]->random=map[cur->random];cur=cur->next;}returnmap[head];}};

复杂度：时间 O(N)，空间 O(N)

解法二：三步法（最优解）⭐⭐⭐

这是最巧妙的解法，不需要额外空间，纯指针操作。

核心思想

三步走：

1. 插入复制节点：在每个原节点后面插入一个复制节点
2. 设置 random 指针：复制节点的random指向原节点random的复制节点
3. 分离链表：将原链表和复制链表分开

Step 1：在每个原节点后面插入复制节点

原链表: A → B → C → NULL 插入后: A → A' → B → B' → C → C' → NULL ↑ ↑ ↑ ↑ ↑ ↑ 原 复 原 复 原 复

代码：

structNode*cur=head;while(cur!=NULL){structNode*copy=(structNode*)malloc(sizeof(structNode));copy->val=cur->val;copy->next=cur->next;cur->next=copy;cur=copy->next;}

Step 2：设置复制节点的 random 指针

关键逻辑：

• 原节点的random指向某个节点
• 复制节点的random应该指向原节点random的复制节点
• 即：copy->random = cur->random->next

原链表: A → B → C ↓ ↓ ↓ null A B 插入复制节点后: A → A' → B → B' → C → C' ↓ ↓ ↓ ↓ ↓ ↓ null null A A' B B' ↑ ↑ cur->random->next B' 就是 B 的复制节点

代码：

cur=head;while(cur!=NULL){structNode*copy=cur->next;if(cur->random!=NULL){copy->random=cur->random->next;}else{copy->random=NULL;}cur=copy->next;}

Step 3：分离两个链表

将混合链表拆分成两个独立的链表。

混合: A → A' → B → B' → C → C' → NULL 分离后: 原链表: A → B → C → NULL 复制链表: A' → B' → C' → NULL

代码：

structNode*newHead=head->next;structNode*copy=newHead;cur=head;while(cur!=NULL){cur->next=copy->next;cur=cur->next;if(cur!=NULL){copy->next=cur->next;copy=copy->next;}}

完整代码

structNode*copyRandomList(structNode*head){if(head==NULL){returnNULL;}// Step 1: 插入复制节点structNode*cur=head;while(cur!=NULL){structNode*copy=(structNode*)malloc(sizeof(structNode));copy->val=cur->val;copy->next=cur->next;cur->next=copy;cur=copy->next;}// Step 2: 设置 random 指针cur=head;while(cur!=NULL){structNode*copy=cur->next;if(cur->random!=NULL){copy->random=cur->random->next;}else{copy->random=NULL;}cur=copy->next;}// Step 3: 分离链表structNode*newHead=head->next;structNode*copy=newHead;cur=head;while(cur!=NULL){cur->next=copy->next;cur=cur->next;if(cur!=NULL){copy->next=cur->next;copy=copy->next;}}returnnewHead;}

图解全过程

以一个具体例子来走一遍：

原链表: [7, null] → [13, 0] → [11, 4] → [10, 2] → [1, 0] ↑ ↑ ↑ ↑ ↑ 索引0 索引1 索引2 索引3 索引4 random=null random→0 random→4 random→2 random→0 注：[val, random_index]

Step 1: 插入复制节点

[7] → [7'] → [13] → [13'] → [11] → [11'] → [10] → [10'] → [1] → [1'] → NULL ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ 0 0' 1 1' 2 2' 3 3' 4 4'

Step 2: 设置 random

原节点 [7] 的 random = null → 复制节点 [7'] 的 random = null ✓ 原节点 [13] 的 random = [7] (索引0) → 复制节点 [13'] 的 random = [7'] (索引0') ✓ 原节点 [11] 的 random = [1] (索引4) → 复制节点 [11'] 的 random = [1'] (索引4') ✓ 原节点 [10] 的 random = [11] (索引2) → 复制节点 [10'] 的 random = [11'] (索引2') ✓ 原节点 [1] 的 random = [7] (索引0) → 复制节点 [1'] 的 random = [7'] (索引0') ✓

Step 3: 分离

原链表: [7] → [13] → [11] → [10] → [1] → NULL 复制链表: [7'] → [13'] → [11'] → [10'] → [1'] → NULL

完美！每个复制节点的random都指向了复制链表中对应的节点。

为什么三步法能 O(1) 空间？

关键点在于利用了原链表本身作为存储空间：

1. 原链表的next指针被暂时"征用"来存储复制节点
2. 复制节点的random可以通过原节点的random+ 偏移 1 找到
3. 不需要额外的哈希表来存储映射关系

这就是"原地"的威力——用链表自身的结构来代替额外数据结构。

常见面试追问

Q1：三步法会破坏原链表吗？

会。第三步分离后，原链表被恢复了（next指向恢复），所以原链表没有被破坏。但如果中途出错，原链表可能被损坏。

Q2：如果要求不能修改原链表，怎么办？

那就只能用哈希表法了。第一遍遍历原链表建立映射，第二遍设置指针。空间复杂度 O(N)。

Q3：如果 random 指针指向的是原链表中不存在的节点？

题目保证了random指向链表中的节点或null，所以不用担心。

Q4：三步法中，为什么copy->random = cur->random->next而不是cur->random？

因为我们要让复制节点指向复制链表中对应的节点，而不是原节点。

原节点 A 的 random 指向 B 复制节点 A' 的 random 应该指向 B'（B 的复制节点） B' 在哪里？在 B 的后面：B->next = B' 所以：A'->random = A->random->next

本系列总结

四篇博客完整覆盖了单链表的核心算法题：

链表解题心法

回顾整个系列，链表题目的核心就这几点：

1. 画图！画图！画图！ 链表题不画图，就像闭着眼睛走路。 2. 哨兵位（dummy） 统一处理头节点，省去特殊判断。 3. 快慢指针 环检测、找中点、找倒数第k个，一招鲜吃遍天。 4. 三指针 反转链表的基本功。 5. 先保存，再修改 修改指针前，先保存后继节点，防止断链。 6. 注意边界条件 空链表、单节点、头节点、尾节点。

结语

单链表的算法题到此就全部讲完了。从最基础的增删改查，到巧妙的快慢指针，再到复杂的随机链表复制，每一步都是对指针操作能力的锤炼。

记住：链表题的答案就在纸上。遇到难题时，画个图，把指针的变化画清楚，代码自然就写出来了。

希望这个系列能帮助你在链表题目的道路上少走弯路。如果觉得有收获，欢迎点赞收藏！

💡最后的小贴士：更多的链表题目可以在 LeetCode 和 牛客网 上继续刷，保持手感，熟能生巧！