对于准备算法考试、刷面试题的人来说，带随机指针的链表复制问题也就是LeetCode 138题，是链表部分面试里经常考到的题型，这道题看上去只是普通的链表深度拷贝，可解题的难点全都在随机指针也就是random的定向赋值上，大部分参加面试的人遇到这道题很容易思路卡住，要么写出的代码步骤繁杂、逻辑啰嗦，要么根本理不清随机指针的赋值方式和关联逻辑。
解决这道题不用死记硬背解题步骤，只要掌握原地复制的三步方法，就能不用额外的哈希表，把空间复杂度优化到最好，不管是笔试时现场手写代码，还是面试时口头讲解思路，都能高效做完这道题。
一、问题定义与基础解析
首先我们要弄明白随机链表的节点组成，这种特殊的链表，每个节点里面都有两种指针，各自的作用如下：
- 后继指针（next）：指向链表的下一个节点，指向规律和普通的单向链表没有任何区别；
- 随机指针（random）：可以指向链表中任意一个有效的节点，也可以直接指向空值null；
这道题的核心要求是完成链表的深度拷贝，简单来说就是新建一条和原链表完全独立的新链表，新链表每个节点的数值、后继指针指向、随机指针指向都要和原链表完全一样，而且整个操作过程不能改动原链表原本的结构。
大家刚开始做这道题常犯的错误思路：
大部分人第一次做这道题，都会先遍历链表复制基础节点，再单独去设置随机指针的指向，这个方法有个致命问题，就是随机指针指向的目标节点可能还没创建出来，没办法精准找到并完成赋值，就算用哈希表存原节点和新节点的对应关系，能解决查找定位的问题，却会占用O(n)的额外内存空间，而面试里一般要求把空间复杂度优化到O(1)，这也是原地三步法更有优势的主要原因。
二、核心解题思路：原地复制三步解法
原地复制方法的核心思路就是在原链表的基础上，直接插入对应的复制节点，靠着原节点和复制节点的位置对应关系，完成随机指针的赋值之后，再把两条链表拆分分开，整个解题过程不用额外用到哈希表，时间复杂度保持在O(n)，空间复杂度也能优化到O(1)，是这道题最优质的解题办法。
接下来会把每一步操作拆解开，结合背后的逻辑原理一起讲解，方便大家理解和记住。
第一步：遍历原链表，插入对应复制节点
这一步主要要达成的目标是，给原链表的每一个节点，都做一个数值完全一样的复制节点，再把复制节点直接插到对应原节点的后面，让原节点和复制节点交替连接，形成两条链表交织在一起的结构。
具体的操作步骤可以分成这几步：
- 定义一个游标指针cur，让它指向原链表的头节点，开始遍历整个链表；
- 新建一个复制节点copy，保证这个节点的数值和当前cur指向的节点完全相同；
- 把复制节点插到原节点和它原本的下一个节点中间，也就是让cur.next指向copy，copy.next指向原节点原来的下一个节点；
- 让游标cur沿着链表往后移动，一直重复上面的操作，直到走到链表的最后一个节点。
这一步做完之后，链表的结构就变成了：原节点1→复制节点1→原节点2→复制节点2→……→原节点n→复制节点n。
这一步的主要作用，就是建立起原节点和复制节点一一对应的位置关系，复制节点就是对应原节点的下一个节点，后续不用映射表也能快速找到两者的对应关系。
第二步：配置复制节点随机指针指向
这一步是整道题的解题关键，也是手写代码时最容易出错的地方，只要理清两者的关联逻辑，只需要记住一条核心的赋值规则就够了：
复制节点的随机指针 = 原节点随机指针指向节点的下一个节点
具体的操作步骤如下：
- 把游标指针cur重新移回原链表的头节点，开始第二轮链表遍历；
- 如果当前原节点的随机指针不是空值，那么对应的复制节点也就是cur.next的随机指针，直接指向cur.random的下一个节点，也就是目标节点对应的复制节点；
- 如果当前原节点的随机指针是空值，直接把对应复制节点的随机指针设为空即可；
- 让游标cur持续往后移动，直到遍历完链表所有节点。
背后的原理很简单，经过第一步的节点插入操作，原节点随机指针指向的节点，它的下一个节点就是对应的复制节点，靠着这种位置关联就能精准完成赋值，彻底解决随机指针指向未创建节点的核心难题。
第三步：拆分交织链表，分离原表与拷贝表
前两步操作全部完成后，复制节点的后继指针和随机指针都已经设置正确，这一步需要把交织在一起的两条链表拆分出来，同时恢复原链表原本的结构，避免原链表的数据结构被损坏。
具体的操作步骤如下：
- 把游标cur再次移回链表头节点，定义copyHead指向复制链表的头节点也就是cur.next，同时新建copy游标用来遍历复制链表；
- 遍历整条交织的链表，执行节点拆分操作，也就是让cur.next=cur.next.next，copy.next=copy.next.next；
- 让cur和copy两个游标同步往后移动，直到遍历完整个链表；
- 最后返回copyHead，这个就是完成深度拷贝后的随机链表头节点。
三、完整代码实现（Java语言版）
下面的代码很适合面试时手写，每一行代码都加了详细注释，能清晰对应每一步的解题逻辑，方便大家理解和记忆：
/*
// 节点结构定义
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
class Solution {
public Node copyRandomList(Node head) {
// 空链表边界值判断
if(head == null){
return null;
}
// 第一步：遍历插入复制节点
Node cur = head;
while(cur != null){
Node copy = new Node(cur.val);
copy.next = cur.next;
cur.next = copy;
cur = copy.next;
}
// 第二步：配置随机指针指向
cur = head;
while(cur != null){
Node copy = cur.next;
// 核心赋值逻辑，规避空指针异常
if(cur.random != null){
copy.random = cur.random.next;
}else{
copy.random = null;
}
cur = copy.next;
}
// 第三步：拆分两条链表，复原原表
cur = head;
Node copyHead = head.next;
Node copy = copyHead;
while(cur != null){
cur.next = copy.next;
cur = cur.next;
if(cur != null){
copy.next = cur.next;
copy = copy.next;
}
}
return copyHead;
}
}
四、面试核心考点与常见失误总结
- 两类解题方案对比（面试高频提问）
- 哈希表映射法：思路简单直白，上手很容易，不用做复杂的指针操作，但是会占用O(n)的额外空间，更适合笔试时快速写出代码解题；
- 原地三步解法：空间复杂度能保持在O(1)，是这道题的最优解法，也是面试里重点考察的方法，能直接看出面试者对链表指针操作的熟练程度。
- 常见犯错情况整理
- 拆分链表的时候，忘了恢复原链表的结构，导致原链表被弄坏；
- 设置随机指针的时候，没有判断原节点随机指针是否为空，导致代码出现空指针报错；
- 遍历链表时，游标移动的逻辑出错，造成节点丢失或者代码陷入死循环。
- 面试追问答题方法
面试的时候，面试官一般都会问：原地解法为什么能做到O(1)的空间复杂度？
标准回答：整个解题过程只用了几个临时的游标指针，没有额外开辟集合、数组这类空间存放节点对应关系，所有操作都在原链表上完成，所以空间复杂度是常数级别。
五、总结与拓展
随机链表复制这道题，本质上考察的就是链表指针的细致操作和深度拷贝的核心逻辑，解题的关键就是搞定随机指针的赋值，只要牢牢记住插入复制节点、设置随机指针、拆分分离链表这三个核心步骤，再多动手练习手写代码，面试遇到同类题型就能轻松应对。
学算法不是死记硬背解题步骤，而是弄懂底层的逻辑，学会一类题的解题方法，后续会持续更新面试常考的数据结构与算法题解析，针对重难点内容做详细的讲解分析。