题目描述

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%的用户

我原以为空间开得挺多，结果比想象的要好