138. Copy List with Random Pointer
使用 hashmap,第一遍建立原节点和新节点的hashmap,第二遍给next和random指针赋值。
Time = O(n), space = O(n)
/*
// Definition for a Node.
class Node {
public int val;
public Node next;
public Node random;
public Node() {}
public Node(int _val,Node _next,Node _random) {
val = _val;
next = _next;
random = _random;
}
};
*/
class Solution {
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
Node cur = head;
Map<Node, Node> map = new HashMap<>();
while (cur != null) {
map.put(cur, new Node(cur.val, null, null));
cur = cur.next;
}
cur = head;
while (cur != null) {
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
return map.get(head);
}
}