題目描述
給定一個鏈表蜂筹，每個節(jié)點包含一個額外增加的隨機指針，該指針可以指向鏈表中的任何節(jié)點或空節(jié)點辫秧。
要求返回這個鏈表的深拷貝般码。
示例：
輸入: {"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}
思路
- 對要拷貝的鏈表進行兩次遍歷妻率。
2.第一次遍歷以原鏈表節(jié)點為key，新建節(jié)點為value將它們存儲再哈希表中板祝。
3.第二次遍歷將新建的節(jié)點取出宫静，并設(shè)置next和random節(jié)點。
Java代碼實現(xiàn)
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);
}
