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;

    }

}