138. Copy List with Random Pointer
C++，hash，链表。看到的都是没用哈希表的版本，我就写一个用了好几个表的版本。
如何在深拷贝的情况下，记录random指针指向的地址其实是一件难事。。。
- 深拷贝要求重新生成结点，而不是单纯地复制指针
- “原表中每个结点的
random指向”，这个信息复制到新表需要通过两个映射- 第i个节点的
random指向第j个节点的映射 - 数字i到第i个节点的映射
- 第i个节点的
- 上述第一个映射需要通过另一个映射实现，即原链表中第i个节点到数字i的映射
利用上述三个映射表，就能比较简单地想到解题思路啦：
class Solution {
public:
Node* copyRandomList(Node* head) {
if (!head) return nullptr;
unordered_map<Node*, int> addr_2_i;
unordered_map<int, int> i_2_i;
unordered_map<int, Node*> i_2_addr;
Node* root = CreateList(head, addr_2_i, i_2_addr, 1);
CreateHash(head, addr_2_i, i_2_i);
Node* it = root;
int index = 1;
while (it) {
it->random = i_2_addr[i_2_i[index++]];
it = it->next;
}
return root;
}
Node* CreateList(Node* node, unordered_map<Node*, int> &addr_2_i, unordered_map<int, Node*> &i_2_addr, int index) {
Node* root = new Node(node->val, nullptr, nullptr);
addr_2_i[node] = index;
i_2_addr[index] = root;
if (node->next)
root->next = CreateList(node->next, addr_2_i, i_2_addr, index + 1);
else
root->next = nullptr;
return root;
}
void CreateHash(Node* node, unordered_map<Node*, int> &addr_2_i, unordered_map<int, int> &i_2_i) {
int index = 1;
while (node) {
i_2_i[index++] = addr_2_i[node->random];
node = node->next;
}
}
};
