单链表算法题四高级应用篇前言前三篇我们分别学习了基础操作移除元素、反转链表、找中点、合并链表进阶技巧链表分割、回文判断、相交链表环与数学环形链表的判断与证明本篇作为系列的最后一篇将讲解链表题目中最具挑战性的一道题——随机链表的复制。这道题被称为链表界的深拷贝它综合了插入节点、指针操作、链表分离等多种技巧是检验链表掌握程度的试金石。终极题目随机链表的复制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: val7, randomnull 节点1: val13, random节点0 节点2: val11, random节点4 节点3: val10, random节点2 节点4: val1, random节点0节点定义structNode{intval;structNode*next;structNode*random;};思路分析这道题的难点在于random指针。如果只有next指针我们只需遍历原链表逐个创建新节点并连接即可// 只有 next 指针的简单复制structNode*copyList(structNode*head){structNode*dummymalloc(sizeof(structNode));structNode*taildummy;structNode*curhead;while(cur!NULL){structNode*copymalloc(sizeof(structNode));copy-valcur-val;tail-nextcopy;tailcopy;curcur-next;}returndummy-next;}但有了random指针问题就复杂了复制节点时它的random指向的是原链表的节点但我们需要它指向复制链表中对应的节点。怎么建立原节点 → 复制节点的映射关系呢三种解法对比解法核心思路时间复杂度空间复杂度哈希表法用哈希表存储映射关系O(N)O(N)三步法在原节点后插入复制节点O(N)O(1)哈希表法简单直观但需要额外空间。三步法更巧妙空间复杂度 O(1)是面试官更欣赏的解法。解法一哈希表法直观易懂核心思路第一遍遍历创建所有新节点用哈希表记录原节点 → 复制节点的映射第二遍遍历设置每个复制节点的next和randomstructNode*copyRandomList(structNode*head){if(headNULL){returnNULL;}// 哈希表原节点 → 复制节点// 在 C 语言中我们可以用数组或自己实现哈希表// 这里为了演示使用一个简单的映射数组假设节点地址范围有限// 实际面试中C 可以用 unordered_mapC 需要自己实现// 由于 C 没有内置哈希表这里展示核心逻辑// 实际代码请参考下面的三步法它是 O(1) 空间的returnNULL;}由于 C 语言没有内置哈希表实际面试中如果使用 C 语言更推荐三步法。如果用 C/Java/Python哈希表法也很常用。C 版本供参考classSolution{public:Node*copyRandomList(Node*head){if(!head)returnNULL;unordered_mapNode*,Node*map;Node*curhead;// 第一遍创建所有节点while(cur){map[cur]newNode(cur-val);curcur-next;}// 第二遍设置 next 和 randomcurhead;while(cur){map[cur]-nextmap[cur-next];map[cur]-randommap[cur-random];curcur-next;}returnmap[head];}};复杂度时间 O(N)空间 O(N)解法二三步法最优解⭐⭐⭐这是最巧妙的解法不需要额外空间纯指针操作。核心思想三步走插入复制节点在每个原节点后面插入一个复制节点设置 random 指针复制节点的random指向原节点random的复制节点分离链表将原链表和复制链表分开Step 1在每个原节点后面插入复制节点原链表: A → B → C → NULL 插入后: A → A → B → B → C → C → NULL ↑ ↑ ↑ ↑ ↑ ↑ 原 复 原 复 原 复代码structNode*curhead;while(cur!NULL){structNode*copy(structNode*)malloc(sizeof(structNode));copy-valcur-val;copy-nextcur-next;cur-nextcopy;curcopy-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 的复制节点代码curhead;while(cur!NULL){structNode*copycur-next;if(cur-random!NULL){copy-randomcur-random-next;}else{copy-randomNULL;}curcopy-next;}Step 3分离两个链表将混合链表拆分成两个独立的链表。混合: A → A → B → B → C → C → NULL 分离后: 原链表: A → B → C → NULL 复制链表: A → B → C → NULL代码structNode*newHeadhead-next;structNode*copynewHead;curhead;while(cur!NULL){cur-nextcopy-next;curcur-next;if(cur!NULL){copy-nextcur-next;copycopy-next;}}完整代码structNode*copyRandomList(structNode*head){if(headNULL){returnNULL;}// Step 1: 插入复制节点structNode*curhead;while(cur!NULL){structNode*copy(structNode*)malloc(sizeof(structNode));copy-valcur-val;copy-nextcur-next;cur-nextcopy;curcopy-next;}// Step 2: 设置 random 指针curhead;while(cur!NULL){structNode*copycur-next;if(cur-random!NULL){copy-randomcur-random-next;}else{copy-randomNULL;}curcopy-next;}// Step 3: 分离链表structNode*newHeadhead-next;structNode*copynewHead;curhead;while(cur!NULL){cur-nextcopy-next;curcur-next;if(cur!NULL){copy-nextcur-next;copycopy-next;}}returnnewHead;}图解全过程以一个具体例子来走一遍原链表: [7, null] → [13, 0] → [11, 4] → [10, 2] → [1, 0] ↑ ↑ ↑ ↑ ↑ 索引0 索引1 索引2 索引3 索引4 randomnull 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 4Step 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) 空间关键点在于利用了原链表本身作为存储空间原链表的next指针被暂时征用来存储复制节点复制节点的random可以通过原节点的random 偏移 1 找到不需要额外的哈希表来存储映射关系这就是原地的威力——用链表自身的结构来代替额外数据结构。常见面试追问Q1三步法会破坏原链表吗会。第三步分离后原链表被恢复了next指向恢复所以原链表没有被破坏。但如果中途出错原链表可能被损坏。Q2如果要求不能修改原链表怎么办那就只能用哈希表法了。第一遍遍历原链表建立映射第二遍设置指针。空间复杂度 O(N)。Q3如果 random 指针指向的是原链表中不存在的节点题目保证了random指向链表中的节点或null所以不用担心。Q4三步法中为什么copy-random cur-random-next而不是cur-random因为我们要让复制节点指向复制链表中对应的节点而不是原节点。原节点 A 的 random 指向 B 复制节点 A 的 random 应该指向 BB 的复制节点 B 在哪里在 B 的后面B-next B 所以A-random A-random-next本系列总结四篇博客完整覆盖了单链表的核心算法题篇目题目核心技巧基础操作篇移除链表元素、反转链表、找中点、合并链表哨兵位、三指针、快慢指针进阶技巧篇链表分割、回文链表、相交链表组合技巧、双指针环与数学篇环形链表 I II快慢指针 数学证明高级应用篇随机链表的复制三步法插入 设置 分离链表解题心法回顾整个系列链表题目的核心就这几点1. 画图画图画图 链表题不画图就像闭着眼睛走路。 2. 哨兵位dummy 统一处理头节点省去特殊判断。 3. 快慢指针 环检测、找中点、找倒数第k个一招鲜吃遍天。 4. 三指针 反转链表的基本功。 5. 先保存再修改 修改指针前先保存后继节点防止断链。 6. 注意边界条件 空链表、单节点、头节点、尾节点。结语单链表的算法题到此就全部讲完了。从最基础的增删改查到巧妙的快慢指针再到复杂的随机链表复制每一步都是对指针操作能力的锤炼。记住链表题的答案就在纸上。遇到难题时画个图把指针的变化画清楚代码自然就写出来了。希望这个系列能帮助你在链表题目的道路上少走弯路。如果觉得有收获欢迎点赞收藏最后的小贴士更多的链表题目可以在 LeetCode 和 牛客网 上继续刷保持手感熟能生巧