题目原型：
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.
基本思路：
题目的意思就是深度复制一个链表，这个链表与普通链表不同之处在于多了一个random指针，这个指针可以指向链表中任何一个元素或者指向NULL。初一看，我们最容易想到那种时间复杂度为O(n2)的做法，但是在OJ上被N/A了。换一种思路，借助map，我们可以把时间复杂度降为O(n)。
public RandomListNode copyRandomList(RandomListNode head)
{
if(head==null)
return head;
RandomListNode newHead = null;
//复制不带random指针的链表和新节点与原节点的联系，利用map存储联系
RandomListNode p = head;
RandomListNode newNode;
RandomListNode q = null;
Map
map = new HashMap
(); while(p!=null) { newNode = new RandomListNode(p.label); newNode.random = null; newNode.next = null; map.put(p, newNode); if(p==head) { newHead = newNode; q = newHead; p = p.next; continue; } q.next = newNode; q = newNode; p = p.next; } //根据关系寻找random指针 p = head; q = newHead; while(p!=null) { if(p.random!=null) { q.random = map.get(p.random); } p = p.next; q = q.next; } return newHead; }