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.
思路：第一遍正常复制链表，同一时候用哈希表保存链表中原始节点和新节点的相应关系，第二遍遍历链表的时候，再复制随机域。
这是一种典型的空间换时间的做法，n个节点，须要大小为O(n)的哈希表，同一时候时间复杂度能够减少到O(n)。
/**
* 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 {
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null) {
return head;
}
HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
RandomListNode res = null;
RandomListNode taiListNode = null;
RandomListNode cur = head;
while (cur != null) {
if (res == null) {
res = new RandomListNode(cur.label);
res.next = res.random = null;
taiListNode = res;
map.put(head, res);
}
else{
taiListNode.next = new RandomListNode(cur.label);
taiListNode = taiListNode.next;
map.put(cur, taiListNode); }
cur = cur.next;
}
taiListNode.next = null;
cur = head;
taiListNode = res;
while (cur != null) {
taiListNode.random = (RandomListNode)map.get((RandomListNode)cur.random);
cur = cur.next;
taiListNode = taiListNode.next;
}
return res;
}
}