方法一
哈希表+两次遍历
class Solution {
public Node copyRandomList(Node head) {
Node dummy = new Node(-1), h = head, d = dummy;
HashMap<Node, Node> map = new HashMap<>();
while(h != null){
d.next = new Node(h.val);
map.put(h, d.next);
h = h.next;
d = d.next;
}
h = head;
d = dummy.next;
while(h != null){
d.random = map.get(h.random);
h = h.next;
d = d.next;
}
return dummy.next;
}
}方法二
拼接与拆分+三次遍历 不使用额外空间
class Solution {
public Node copyRandomList(Node head) {
if(head == null) return null;
Node dummy = new Node(-1), h = head, d = dummy;
// 在每个节点后面复制一次
while(h != null){
Node tmp = new Node(h.val);
tmp.next = h.next;
h.next = tmp;
h = h.next.next;
}
// 修改复制节点的random指针
h = head;
while(h != null){
if(h.random != null) h.next.random = h.random.next;
h = h.next.next;
}
// 拆分
h = head;
dummy.next = h.next;
d = h.next;
while(h.next.next != null){ // 最后一个节点不处理了
h.next = h.next.next;
d.next = d.next.next;
h = h.next;
d = d.next;
}
h.next = null; // 单独处理最后一个节点
return dummy.next;
}
}方法三
回溯 + 哈希表
class Solution {
HashMap<Node, Node> map = new HashMap<>();
public Node copyRandomList(Node head) {
if(head == null) return null;
if(!map.containsKey(head)){
Node newHead = new Node(head.val);
map.put(head, newHead);
newHead.next = copyRandomList(head.next);
newHead.random = copyRandomList(head.random);
}
return map.get(head);
}
}