涉及一个知识点，深拷贝与浅拷贝。
| 特性 | 深拷贝 (Deep Copy) | 浅拷贝 (Shallow Copy) |
|---|---|---|
| 定义 | 创建一个新对象，并递归复制所有成员及其指向的资源 | 仅复制指针值，新旧对象共享同一块内存 |
| 内存管理 | 新旧对象完全独立，修改互不影响 | 修改任一对象会影响另一个（可能导致双重释放或内存泄漏） |
| 性能 | 较慢（需分配新内存并复制数据） | 极快（仅复制指针） |
| 使用场景 | 需要完全独立的副本（如复杂链表、树、含指针的结构体） | 临时共享数据，无需修改原对象 |
| 示例 | std::vector v2 = v1; （元素逐个复制） | int* p2 = p1; （仅复制指针） |
示例代码:
class Example {
public:
int* data;
Example(int val) { data = new int(val); }
~Example() { delete data; }
// 浅拷贝（默认拷贝构造函数）
Example(const Example& other) : data(other.data) {}
// 深拷贝
Example(const Example& other) : data(new int(*other.data)) {}
};
int main() {
// 深拷贝，就是new新的节点出来。
Example e1(10);
Example e2 = e1; // 浅拷贝：e2.data 和 e1.data 指向同一内存
*e2.data = 20; // 修改 e2 会影响 e1！
Example e3(e1); // 深拷贝：e3.data 是新的内存
*e3.data = 30; // 修改 e3 不会影响 e1
return 0;
}
解法1：哈希表
摘自牛客题解：
- 假如链表没有随机指针, 我们的拷贝方式很简单, 只要先创建一个哨兵节点, 然后遍历一下给定链表, 创建新节点, 并不断和上个节点连接
- 本题的难点就在于每个节点还有一个指向空或其它节点的指针, 一种比较直观的想法就是先把整条链表连起来, 然后再挨着改变指针, 因此我们可以用哈希表来存放指针的映射关系, 然后根据将随机指针指向原链表随机指针映射在新链表的位置
- 算法实现：首先创建一个哨兵节点, 遍历一次原链表, 先将除随机指针外的部分创建并连接, 同时用哈希表记录指针之间的映射, 最后遍历一次哈希表, 将随机指针指向对应的位置
PS：map和unordered_map的差别和使用：map和unordered_map的差别和使用_unorderedmap和map的区别-CSDN博客
对于查找问题，unordered_map会更加高效一些。
| 操作 | std::map (红黑树) | std::unordered_map (哈希表) |
|---|---|---|
| 插入/删除/查找 | O(log n) | 平均 O(1)，最坏 O(n) |
| 遍历 | 有序遍历（中序遍历） | 无序遍历 |
| 空间复杂度 | 较低（无额外哈希开销） | 较高（需维护哈希桶和负载因子） |
#include <unordered_map>
class Solution {
public:
RandomListNode* Clone(RandomListNode* pHead) {
if (!pHead) return nullptr;
std::unordered_map<RandomListNode*, RandomListNode*> nodeMap;
// 第一次遍历：创建所有新节点并建立映射
RandomListNode* current = pHead;
while (current) {
// key:old node; value:new node
nodeMap[current] = new RandomListNode(current->label);
current = current->next;
}
// 第二次遍历：设置新节点的next和random指针
current = pHead;
while (current) {
if (current->next) {
// 上一步添加的键值对，值之间是没有指向关系的，要设置新节点的next指针
nodeMap[current]->next = nodeMap[current->next];
}
if (current->random) {
nodeMap[current]->random = nodeMap[current->random];
}
current = current->next;
}
return nodeMap[pHead];
}
};
此法空间复杂度为On，时间复杂度为On。
法2
摘自牛客题解：
- 主要思路是将原链表的结点对应的拷贝节点连在其后, 最后链表变成 原1 -> 拷1 -> 原2 -> 拷2 -> … -> null 的形式
- 然后再逐步处理对应的随机指针, 使用双指针, 一个指针指向原链表的节点, 一个指向拷贝链表的节点, 那么就有 拷->random = 原->random->next (random不为空)
- 最后再用双指针将两条链表拆分即可
此法的空间复杂度为O1，无需额外的辅助空间
class Solution {
public:
RandomListNode* Clone(RandomListNode* pHead) {
if (!pHead) return nullptr;
// 第一步：在每个节点后面插入复制节点
RandomListNode* current = pHead;
while (current) {
RandomListNode* clone = new RandomListNode(current->label);
clone->next = current->next;
current->next = clone;
current = clone->next;
}
// 第二步：设置复制节点的random指针
current = pHead;
while (current) {
if (current->random) {
// 跟在原节点后面的是新节点，新节点的random 指向 原节点random后面的
current->next->random = current->random->next;
}
current = current->next->next;
}
// 第三步：拆分两个链表
current = pHead;
RandomListNode* cloneHead = pHead->next;
RandomListNode* cloneCurrent = cloneHead;
while (current) {
current->next = current->next->next;
if (cloneCurrent->next) {
cloneCurrent->next = cloneCurrent->next->next;
}
current = current->next;
cloneCurrent = cloneCurrent->next;
}
return cloneHead;
}
};