# LeetCode-Copy List with Random Pointer

## 题目：

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.

Example 1:

```Input:
{"\$id":"1","next":{"\$id":"2","next":null,"random":{"\$ref":"2"},"val":2},"random":{"\$ref":"2"},"val":1}

Explanation:
Node 1's value is 1, both of its next and random pointer points to Node 2.
Node 2's value is 2, its next pointer points to null and its random pointer points to itself.
```

Note:

1. You must return the copy of the given head as a reference to the cloned list.

## 解题1：

节点中存在随机节点， 由于是随机节点指向下一个节点的随机性， 拷贝时建议next与random新老地址的映射关系。实现1：建立hash表创建关系，拷贝后next和random都从hash表中获取对应的拷贝值的地址即可。

## 实现1：

``````/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;

Node() {}

Node(int _val, Node* _next, Node* _random) {
val = _val;
next = _next;
random = _random;
}
};
*/
class Solution {
public:
return nullptr;
}
unordered_map<Node*, Node*>m;
while (cur != nullptr){
Node *node = new Node(cur->val, nullptr, nullptr);
m[cur] = node;
cur = cur->next;
}
while(cur != nullptr){
m[cur]->next = m[cur->next];
m[cur]->random = m[cur->random];
cur = cur->next;
}

}
};

Runtime: 40 ms
Memory Usage: 22.4 MB

``````

## 解题2：

递归方式判断hash表中是否存在映射关系， 存在返回， 否则复制节点并建立映射关系，之后按照同样方式处理next和random

## 实现2：

``````
class Solution {

public:
unordered_map<Node*, Node*>m;
return nullptr;
}
}
Node *node = new Node(head->val, nullptr, nullptr);
if (NULL == node){
return nullptr;
}
return node;

}
};
Runtime: 28 ms
Memory Usage: 22.6 MB

## 解题3：

复制链表节点，放入当前节点后；遍历复制节点，赋值新节点的random，新节点random所指向节点，就是原有节点random所指节点的next （新节点拷贝了原有节点后）；断开链接返回拷贝后的节点。

## 实现3：

``````class Solution {

public:

return nullptr;
}
//copy
while(cur){
Node *node = new Node(cur->val, nullptr, nullptr);
node->next = cur->next;
cur->next = node;
cur=node->next;
}

//set random
while(cur){
if (cur->random){
cur->next->random = cur->random->next;
}
cur=cur->next->next;
}

while(cur){
Node *copy = cur->next;
cur->next = copy->next;
if (copy->next) {
copy->next = copy->next->next;
}
cur=cur->next;
}
return res;

}
};

Runtime: 28 ms
Memory Usage: 22.2 MB

## 参考：

C++ simple recursive solution

A solution with constant space complexity O(1) and linear time complexity O(N)