Copy List with Random Pointer

題目原型：

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;
	}