A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
解题思路：
思路一：创建链表拷贝，同时使用一个Map存储所有节点数据。再次遍历链表，根据每个节点中random的指向，设定新链表中节点的random指向。
思路二：参考网上解法。1.在链表中依次插入每个节点；2.更新所有新插入节点的random指向；3.把新的所有节点抽取出来，形成链表拷贝。
解法一：
/**
* Definition for singly-linked list with a random pointer.
* class RandomListNode {
* int label;
* RandomListNode next, random;
* RandomListNode(int x) { this.label = x; }
* };
*/
public class Solution {
/**
* @param head: The head of linked list with a random pointer.
* @return: A new head of a deep copy of the list.
*/
public RandomListNode copyRandomList(RandomListNode head) {
Map<Integer, RandomListNode> map = new HashMap<Integer, RandomListNode>();
RandomListNode chead = createList(map, head);
RandomListNode p = chead;
while (head != null) {
if (head.random != null)
p.random = map.get(head.random.label);
head = head.next;
p = p.next;
}
return chead;
}
RandomListNode createList(Map<Integer, RandomListNode> map, RandomListNode node) {
if (node == null)
return null;
RandomListNode cnext = null;
if (node.next != null)
cnext = createList(map, node.next);
RandomListNode cnode = new RandomListNode(node.label);
cnode.next = cnext;
map.put(node.label, cnode);
return cnode;
}
}
解法二：
/**
* Definition for singly-linked list with a random pointer.
* class RandomListNode {
* int label;
* RandomListNode next, random;
* RandomListNode(int x) { this.label = x; }
* };
*/
public class Solution {
/**
* @param head: The head of linked list with a random pointer.
* @return: A new head of a deep copy of the list.
*/
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null)
return null;
RandomListNode p = head;
while (p != null) {
RandomListNode np = new RandomListNode(p.label);
np.next = p.next;
p.next = np;
p = np.next;
}
p = head;
while (p != null) {
if (p.random != null)
p.next.random = p.random.next;
p = p.next.next;
}
p = head.next;
while (p != null) {
if (p.next != null)
p.next = p.next.next;
p = p.next;
}
return head.next;
}
}