【每日算法】LeetCode138. 随机链表的复制-育师

对前端开发者而言，学习算法绝非为了“炫技”。它是你从“页面构建者”迈向“复杂系统设计者”的关键阶梯。它将你的编码能力从“实现功能”提升到“设计优雅、高效解决方案”的层面。从现在开始，每天投入一小段时间，结合前端场景去理解和练习，你将会感受到自身技术视野和问题解决能力的质的飞跃。------ 算法：资深前端开发者的进阶引擎

138. 随机链表的复制：从链表到图的深拷贝思维

1. 题目描述

给定一个长度为n的链表，每个节点除了包含一个val字段和一个指向下一个节点的next指针外，还包含一个可指向链表中任意节点或null的random指针。

请完成这个链表的深拷贝。深拷贝应该完全复制原链表的所有节点及其关系（包括next和random指针），返回复制链表的头节点。

示例：

// 原始链表结构constnode1={val:7,next:node2,random:null};constnode2={val:13,next:node3,random:node1};constnode3={val:11,next:node4,random:node5};constnode4={val:10,next:node5,random:node3};constnode5={val:1,next:null,random:node1};

2. 问题分析

这是一个典型的数据结构深拷贝问题，特殊之处在于每个节点有两个指针，其中一个 (random) 可以指向链表中的任意节点，形成了潜在的图结构（而非简单的线性结构）。

核心挑战：

random指针可能指向尚未创建的节点，也可能形成循环引用
需要保持新链表节点间的对应关系，避免重复创建同一原始节点的多个副本
本质上是对一个有向图的遍历和复制问题

前端视角：
这类似于在前端中深拷贝一个包含循环引用的复杂对象。例如，一个组件树中某个组件引用了另一个组件，两个组件又互相引用的情况。

3. 解题思路

3.1 哈希表映射法（最优解）

使用哈希表建立原节点到新节点的映射关系：

第一次遍历：创建所有新节点并存入哈希表，建立原节点→新节点的映射
第二次遍历：根据哈希表设置新节点的next和random指针

时间复杂度：O(n)
空间复杂度：O(n)

3.2 原地修改拆分法

不额外使用哈希表，通过修改原链表结构实现：

在每个原节点后插入对应的复制节点
设置复制节点的random指针
拆分两个链表，恢复原链表结构

时间复杂度：O(n)
空间复杂度：O(1)（不考虑输出占用的空间）

4. 各思路代码实现

4.1 哈希表映射法

/** * @param {Node} head * @return {Node} */constcopyRandomList=function(head){if(!head)returnnull;constmap=newMap();letcurr=head;// 第一遍遍历：创建所有新节点并建立映射while(curr){map.set(curr,newNode(curr.val));curr=curr.next;}// 第二遍遍历：连接指针curr=head;while(curr){constnewNode=map.get(curr);if(curr.next)newNode.next=map.get(curr.next);if(curr.random)newNode.random=map.get(curr.random);curr=curr.next;}returnmap.get(head);};

4.2 原地修改拆分法

/** * @param {Node} head * @return {Node} */constcopyRandomList=function(head){if(!head)returnnull;// 1. 在每个节点后插入复制节点letcurr=head;while(curr){constcopy=newNode(curr.val);copy.next=curr.next;curr.next=copy;curr=copy.next;}// 2. 设置复制节点的random指针curr=head;while(curr){if(curr.random){curr.next.random=curr.random.next;}curr=curr.next.next;}// 3. 拆分两个链表constdummy=newNode(0);letcopyCurr=dummy;curr=head;while(curr){copyCurr.next=curr.next;copyCurr=copyCurr.next;// 恢复原链表curr.next=curr.next.next;curr=curr.next;}returndummy.next;};

5. 各实现思路的复杂度、优缺点对比

方法	时间复杂度	空间复杂度	优点	缺点	适用场景
哈希表映射法	O(n)	O(n)	逻辑清晰，易于理解；不修改原链表	需要额外O(n)空间存储映射关系	大多数场景，尤其是不能修改原链表的场景
原地修改拆分法	O(n)	O(1)	空间效率高；不需要额外数据结构	修改原链表结构；代码逻辑相对复杂	内存受限且允许修改原链表的场景

6. 总结

6.1 算法核心要点

图的深拷贝思维：随机链表本质上是一个有向图，需要避免循环引用和重复创建
映射关系的维护：无论是哈希表还是原地插入，核心都是建立原节点到新节点的对应关系
两次遍历模式：创建节点→连接指针，这是解决此类问题的通用模式

6.2 前端应用场景

6.2.1 复杂对象深拷贝

在处理包含循环引用的复杂对象时，可以借鉴这种思路：

// 类似思路的深拷贝函数functiondeepClone(obj,map=newMap()){if(!obj||typeofobj!=='object')returnobj;if(map.has(obj))returnmap.get(obj);constclone=Array.isArray(obj)?[]:{};map.set(obj,clone);for(constkeyinobj){if(obj.hasOwnProperty(key)){clone[key]=deepClone(obj[key],map);}}returnclone;}