在本篇文章中，我们将解析题目 "复制带随机指针的链表"，要求在给定一个带随机指针的链表的情况下，进行深拷贝并返回复制链表的头节点。我们将会探讨如何设计一个满足题目要求的算法，逐步展开这个问题的解决方案。
解析题意
题目要求对一个带有随机指针的链表进行深拷贝，复制链表中的节点值、next 指针和 random 指针都应指向复制链表中的新节点。我们需要设计一个算法，满足这些条件，输入为原链表的头节点 head。
奇妙思路
我们可以使用哈希表来建立原链表节点和复制链表节点的映射关系，这样在构建复制链表时就能方便地处理随机指针的拷贝。具体步骤如下：
第一遍遍历：创建复制链表的新节点，并将新节点和原节点的对应关系存入哈希表。
第二遍遍历：根据哈希表的映射关系，复制原链表节点的 next 和 random 指针。
代码实现
以下是用 C++ 实现复制带随机指针的链表的代码：
#include <unordered_map>
class Node {
public:
int val;
Node* next;
Node* random;
Node(int val) : val(val), next(nullptr), random(nullptr) {}
};
class Solution {
public:
Node* copyRandomList(Node* head) {
if (!head) return nullptr;
std::unordered_map<Node*, Node*> nodeMap; // 原节点和复制节点的映射关系
// 第一遍遍历：创建复制链表的新节点
Node* curr = head;
while (curr) {
nodeMap[curr] = new Node(curr->val);
curr = curr->next;
}
// 第二遍遍历：复制 next 和 random 指针
curr = head;
while (curr) {
if (curr->next) {
nodeMap[curr]->next = nodeMap[curr->next];
}
if (curr->random) {
nodeMap[curr]->random = nodeMap[curr->random];
}
curr = curr->next;
}
return nodeMap[head];
}
};
妙趣例证
假设原链表为：1 -> 2 -> 3 -> 4，且随机指针关系为 1.random 指向 3，2.random 指向 1，3.random 指向 4，4.random 指向 2。经过调用 copyRandomList 后，复制链表也会得到相应的复制节点以及对应的随机指针关系。
深入探索
这个问题中，利用哈希表的映射关系帮助我们在第二遍遍历时能够方便地找到复制链表中节点的对应关系。这个方法虽然使用了额外的空间，但确实是一个高效且易于理解的解决方案。
