题目描述
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:
val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.
Example 1:
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Example 2:
Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]
Example 3:
Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解法
分析一下，因为有随机指针，所以遍历一遍不能完成随机指针的复制（如果随机指针指向链表后部的节点，在遍历一遍的情况下，新链表无法得知后部节点）。我们需要遍历两遍，遍历第一遍时，我们需要将随机指针的index记录下来，同时将新节点按顺序保存在vector，第二遍遍历新链表，在对应的index获得random值。
代码
Node* copyRandomList(Node* head) {
if (!head) return NULL;
unordered_map<Node*, int> node_index;
vector<Node*> node_vector;
Node* node = head;
int index = 0;
Node* parent = NULL;
Node* new_head = NULL;
while (node) {
node_index.insert(make_pair(node, index));
Node* new_node = new Node(node->val);
if (parent)
parent->next = new_node;
node_vector.push_back(new_node);
if (parent == NULL)
new_head = new_node;
parent = new_node;
node = node->next;
index++;
}
node = new_head;
auto origin_node = head;
while (node) {
auto r = node_index.find(origin_node->random);
if (r != node_index.end()) {
index = r->second;
}
else {
index = -1;
}
node->random = index >= 0 ? node_vector[index] : NULL;
node = node->next;
origin_node = origin_node->next;
}
return new_head;
}
运行结果
执行用时 :16 ms, 在所有 C++ 提交中击败了60.63%的用户
内存消耗 :13.7 MB, 在所有 C++ 提交中击败了69.36%的用户
我原以为空间开得挺多，结果比想象的要好