题目描述
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的深拷贝。
示例：
输入: {"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}
思路
- 对要拷贝的链表进行两次遍历。
2.第一次遍历以原链表节点为key，新建节点为value将它们存储再哈希表中。
3.第二次遍历将新建的节点取出，并设置next和random节点。
Java代码实现
public Node copyRandomList(Node head) {
Map<Node,Node> nodeMap = new HashMap();
Node p = head;
while(p != null){
nodeMap.put(p,new Node(p.val));
p = p.next;
}
p = head;
while(p != null){
nodeMap.get(p).next = nodeMap.get(p.next);
nodeMap.get(p).random = nodeMap.get(p.random);
p = p.next;
}
return nodeMap.get(head);
}
