C++算法
复制带随机指针的链表：LeetCode 138 题解法
介绍 LeetCode 138 题“复制带随机指针的链表”的解法。题目要求深拷贝一个包含 random 指针的单链表。难点在于 random 指针指向任意节点，直接复制难以建立映射关系。提出三步原地复制法：第一步在原节点后插入复制节点；第二步修正复制节点的 random 指针；第三步拆分链表恢复原状并得到新链表。该方法时间复杂度为 O(n)，空间复杂度为 O(1)，无需哈希表辅助，是解决此类问题的经典高效方案。
介绍 LeetCode 138 题“复制带随机指针的链表”的解法。题目要求深拷贝一个包含 random 指针的单链表。难点在于 random 指针指向任意节点，直接复制难以建立映射关系。提出三步原地复制法：第一步在原节点后插入复制节点；第二步修正复制节点的 random 指针；第三步拆分链表恢复原状并得到新链表。该方法时间复杂度为 O(n)，空间复杂度为 O(1)，无需哈希表辅助，是解决此类问题的经典高效方案。
给定一个单链表，每个节点除了包含一个 next 指针指向下一个节点，还包含一个 random 指针，该指针可以随机指向链表中的任意一个节点，也可以指向 NULL。要求完整复制出这个链表的深拷贝，新链表的每个节点都是全新的节点，且 next 和 random 指针的指向关系与原链表完全一致。
普通链表复制的核心是按序遍历处理 next 指针，而本题的关键痛点在于：原节点的 random 指针指向的位置是随机的，复制节点无法直接确定自己的 random 指针该指向哪个新节点。如果先单独复制所有节点再处理 random 指针，需要额外的哈希表存储原节点与复制节点的映射关系，而本文的三步法无需额外空间（空间复杂度 O(1)），是更优的解法。
首先定义题目中的链表节点结构，这是代码实现的基础：
// 定义带随机指针的链表节点
struct Node {
int val;
Node* next;
Node* random;
Node(int x) : val(x), next(NULL), random(NULL) {}
};
本次解题的核心思路是原地插入复制节点→修正复制节点的 random 指针→拆分原链表与复制链表，全程在原链表上操作，无需额外的哈希表存储映射，时间复杂度 O(n)，空间复杂度 O(1)（仅使用常数个指针变量）。
为了更直观理解算法步骤，我们以原链表 1 → 2 → 3 → NULL 为例，其中原节点 1 的 random 指向 3，原节点 2 的 random 指向 1，原节点 3 的 random 指向 NULL，通过图形一步步拆解算法执行过程。
核心操作：遍历原链表，在每个原节点的后面插入一个值相同、random 指针暂时与原节点一致的复制节点，使原链表变为 原节点→复制节点→原节点→复制节点 的成对结构。
操作目的：让复制节点与原节点形成一一对应的紧邻关系，为后续修正 random 指针提供便利，通过'原节点的 random 指向→原节点 random 的下一个节点'，即可找到复制节点的正确 random 指向。
原链表：
1 → 2 → 3 → NULL
| | |
v v v
3 1 NULL
插入复制节点后（复制节点标为 1'、2'、3'）：
1 → 1' → 2 → 2' → 3 → 3' → NULL
| | | | | |
v v v v v v
3 3 1 1 NULL NULL
可以看到，复制节点的 random 指针暂时和原节点指向相同，后续需要修正。
// 步骤 1：在每个原节点后插入复制节点
Node* p = head;
while (p != NULL) {
Node* copy = new Node(p->val); // 复制原节点的值
copy->random = p->random; // 暂时让复制节点的 random 与原节点一致
copy->next = p->next; // 复制节点的 next 指向原节点的下一个节点
p->next = copy; // 原节点的 next 指向复制节点
p = copy->next; // p 跳转到下一个原节点，继续遍历
}
核心操作：遍历插入后的链表，仅处理复制节点的 random 指针：若原节点的 random 指向节点 A，那么复制节点的 random 应指向 A 的复制节点 A'，而 A' 正是 A 的下一个节点，因此只需将复制节点的 random 指向 原 random 指向的节点的 next 即可。
注意点：需要判断原节点的 random 是否为 NULL，若为 NULL，复制节点的 random 也保持 NULL，无需处理。
待修正的链表（复制节点 random 未修正）：
1 → 1' → 2 → 2' → 3 → 3' → NULL
| | | | | |
v v v v v v
3 3 1 1 NULL NULL
修正后（复制节点 random 指向对应复制节点）：
1 → 1' → 2 → 2' → 3 → 3' → NULL
| | | | | |
v v v v v v
3 3' 1 1' NULL NULL
此时，所有复制节点的 next 和 random 指针均已指向正确位置，仅剩最后一步拆分。
// 步骤 2：修正复制节点的 random 指针
p = head->next; // p 指向第一个复制节点
while (p != NULL) {
if (p->random != NULL) { // 若原 random 不为空，才需要修正
p->random = p->random->next;
}
// p 跳转到下一个复制节点（隔一个节点）
p = (p->next != NULL) ? p->next->next : NULL;
}
核心操作：遍历成对的链表，将 原节点→复制节点→原节点→复制节点 的结构拆分为原链表（原节点依次连接）和复制链表（复制节点依次连接），恢复原链表的同时，得到独立的复制链表。
操作技巧：设置两个指针分别指向原节点和复制节点，依次遍历并调整 next 指针，最终复制链表的头节点为原链表头节点的下一个节点（head->next）。
待拆分的链表（已修正 random）：
1 → 1' → 2 → 2' → 3 → 3' → NULL
| | | | | |
v v v v v v
3 3' 1 1' NULL NULL
拆分后：
原链表：1 → 2 → 3 → NULL（恢复原状）
复制链表：1' → 2' → 3' → NULL（最终结果）
// 步骤 3：拆分原链表和复制链表
Node* newHead = head->next; // 复制链表的头节点
Node* p1 = head; // p1 指向原节点
Node* p2 = newHead; // p2 指向复制节点
while (p1 != NULL) {
p1->next = p2->next; // 原节点的 next 指向下一个原节点
p1 = p1->next; // p1 后移
if (p1 != NULL) { // 若原节点未到末尾，复制节点继续后移
p2->next = p1->next;
p2 = p2->next;
}
}
return newHead; // 返回复制链表的头节点
结合上述三步法，补充空链表判断等边界条件处理，给出完整的 C++ 代码实现，代码逻辑清晰，注释详尽，可直接在力扣提交通过：
#include <iostream>
using namespace std;
// 定义带随机指针的链表节点
struct Node {
int val;
Node* next;
Node* random;
Node(int x) : val(x), next(NULL), random(NULL) {}
};
class Solution {
public:
Node* copyRandomList(Node* head) {
// 边界条件：空链表直接返回 NULL
if (head == NULL) {
return NULL;
}
// 步骤 1：在每个原节点后插入复制节点
Node* p = head;
while (p != NULL) {
Node* copy = new Node(p->val);
copy->random = p->random;
copy->next = p->next;
p->next = copy;
p = copy->next;
}
// 步骤 2：修正复制节点的 random 指针
p = head->next;
while (p != NULL) {
if (p->random != NULL) {
p->random = p->random->next;
}
p = (p->next != NULL) ? p->next->next : NULL;
}
// 步骤 3：拆分原链表和复制链表
Node* newHead = head->next;
Node* p1 = head;
Node* p2 = newHead;
while (p1 != NULL) {
p1->next = p2->next;
p1 = p1->next;
if (p1 != NULL) {
p2->next = p1->next;
p2 = p2->next;
}
}
newHead;
}
};
{
Node* p = head;
(p != ) {
cout << << p->val;
(p->random != ) {
cout << << p->random->val << endl;
} {
cout << << endl;
}
p = p->next;
}
}
{
Node* n1 = ();
Node* n2 = ();
Node* n3 = ();
n1->next = n2;
n2->next = n3;
n1->random = n3;
n2->random = n1;
n3->random = ;
Solution s;
Node* copyHead = s.(n1);
cout << << endl;
(copyHead);
;
}
算法全程对链表进行三次遍历：插入复制节点一次、修正 random 指针一次、拆分链表一次。每次遍历的时间复杂度为 O(n)，总时间复杂度为 O(n)（时间复杂度不考虑常数项，3n 最终简化为 n）。
算法仅使用了常数个指针变量（p、p1、p2、newHead 等），未使用额外的数组、哈希表等数据结构，所有操作均在原链表上完成，因此空间复杂度为 O(1)。
除了本次的三步法，解决该问题还有哈希表映射法：先复制所有节点，用哈希表存储 原节点→复制节点 的映射，再遍历处理 next 和 random 指针。该方法的时间复杂度也是 O(n)，但空间复杂度为 O(n)（需要存储 n 个节点的映射），相比之下，三步法是更优的原地解法。
random 指针为 NULL 的情况，避免空指针异常。本题的三步法是链表原地操作的经典应用，这类思路还可迁移到其他链表问题中，例如：
掌握链表的指针操作技巧，理解'分步骤处理'和'原地操作'的思想，能让我们更轻松地应对各类链表算法题。力扣 138 题作为基础经典题，是锻炼链表思维的绝佳素材，吃透这道题，后续的复杂链表问题也能迎刃而解！
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online