新建Node物體類
public class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
哈希表
public static Node copyRandomList(Node head) {
if (head==null)
return null;
//哈希表中，key是原來的節點，value是現在的
Map<Node,Node> hashMap=new HashMap<>();
Node p=head;
//將原節點放入哈希表中
while (p!=null){
Node newNode=new Node(p.val);
hashMap.put(p,newNode);
p=p.next;
}
p=head;
//遍歷原鏈表，設定新節點的next和random
while (p!=null){
//p是原節點，get(p)就是新的節點
Node newNode=hashMap.get(p);
if(p.next!=null){
newNode.next=hashMap.get(p.next);
}
//p.random表示原節點隨機指向
//hashMap中：
// hashMap.get(p.random)表示hashMap.get(p)對應的新節點
if (p.random!=null){
newNode.random=hashMap.get(p.random);
}
p=p.next;
}
//回傳原節點對應的新節點
return hashMap.get(head);
}
我有點懵逼，為什么是0ms，顯示通過了，我一度懷疑是不是沒執行，提交了好幾次，頭一次看到100%，難以言語，
哈希表與鏈表
- 先將原節點放入哈希表中，map.put(p,newNode);
- 再通過哈希表中原新節點，設定新的指向
- newNode.next = map.get(p.next);
- newNode.random = map.get(p.random);
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/208527.html
標籤：其他