# 138. Copy List with Random Pointer(138. Copy List with Random Pointer)-其他

## 138. Copy List with Random Pointer(138. Copy List with Random Pointer)

``````    public Node copyRandomList(Node head) {
return null;
Map<Node, Node> map = new HashMap<>();
return res;
}

private void clone(Node oldNode, Node newNode, Map<Node, Node> map) {
map.put(oldNode, newNode);
if (oldNode.next != null) {
newNode.next = new Node(oldNode.next.val);
clone(oldNode.next, newNode.next, map);
}
}

private void randomLink(Node oldNode, Node newNode, Map<Node, Node> map) {
if (oldNode.random != null) {
newNode.random = map.get(oldNode.random);
}
if (oldNode.next != null) {
}
}``````
————————

This problem is very complicated at first. It requires both clone node and clone random link, but in fact, it can be easily solved by using a HashMap. The following is my algorithm. First clone node and next link of node, and then random link of clone node. The time complexity is O (n):

``````    public Node copyRandomList(Node head) {
return null;
Map<Node, Node> map = new HashMap<>();
return res;
}

private void clone(Node oldNode, Node newNode, Map<Node, Node> map) {
map.put(oldNode, newNode);
if (oldNode.next != null) {
newNode.next = new Node(oldNode.next.val);
clone(oldNode.next, newNode.next, map);
}
}

private void randomLink(Node oldNode, Node newNode, Map<Node, Node> map) {
if (oldNode.random != null) {
newNode.random = map.get(oldNode.random);
}
if (oldNode.next != null) {