【每日算法】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 哈希表映射法（最优解）

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

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

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

3.2 原地修改拆分法

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

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

时间复杂度：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. 各实现思路的复杂度、优缺点对比

6. 总结

6.1 算法核心要点

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

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;}

6.2.2 组件/节点复制

• UI组件树的复制：当组件间存在相互引用时，需要类似的映射机制
• DOM节点复制与操作：复制复杂的DOM结构并保持事件监听器等引用关系
• 状态管理：在Redux或Vuex中复制包含循环引用的状态树

6.2.3 数据流处理

• 复杂数据结构的序列化/反序列化：如处理嵌套评论、回复关系
• 图数据库查询结果的复制：保持节点间的关系不变

6.3 思维提升价值

1. 从线性到非线性思维：链表→图，这是数据结构认知的重要升级
2. 空间换时间的权衡：哈希表法是典型的空间换时间策略
3. 原地算法设计：在不使用额外空间的情况下解决问题，这对性能敏感的前端应用（如图形编辑器、游戏）尤为重要

通过这道题，我们不仅学会了一个具体算法，更重要的是掌握了处理复杂引用关系、循环引用的通用思维模型。这种能力在前端优化、复杂状态管理、性能调优等方面都有广泛应用，是从初级前端迈向资深开发的重要标志。