深度拷贝带随机指针的链表
解法1:
public Node copyRandomList(Node head) {
if(head == null) {
return null;
}
Map map = new HashMap();
Node newHead = head;
//先深度拷贝node 节点,使用HashMap
while (newHead != null) {
if (!map.containsKey(newHead)) {
Node node = new Node(newHead.val);
map.put(newHead, node);
}
if (newHead.random != null) {
Node random = newHead.random;
if (!map.containsKey(random)) {
Node copyRandom = new Node(random.val);
map.put(random, copyRandom);
}
map.get(newHead).random = map.get(random);
}
newHead = newHead.next;
}
//从头开始,从HashMap拿出弄得,组装新链表
newHead = head;
while (newHead != null) {
Node next = newHead.next;
map.get(newHead).next = map.get(next);
newHead = newHead.next;
}
return map.get(head);
}
解法2:
class Solution2 {
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
copy(head);
copyRandom(head);
return split(head);
}
public void copy(Node head) {
Node node = head;
while(node != null) {
Node copy = new Node(node.val);
copy.next = node.next;
node.next = copy;
node = copy.next;
}
}
public void copyRandom(Node head) {
Node node = head;
while(node != null && node.next != null) {
if (node.random != null) {
node.next.random = node.random.next;
}
node = node.next.next;
}
}
public Node split(Node head) {
Node result = head.next;
Node move = head.next;
while(head != null && head.next != null) {
head.next = head.next.next;
head = head.next;
if (move != null && move.next != null) {
move.next = move.next.next;
move = move.next;
}
}
return result;
}
}



