Description:
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.
Link:
[http://www.lintcode.com/en/problem/copy-list-with-random-pointer/]
解題思路：
解法1：O(n) space, DFS
使用哈希表儲存已經(jīng)克隆的節(jié)點，當在哈希表中找到節(jié)點的時候直接使用茧泪，否則就創(chuàng)新的節(jié)點。
解法2：O(1) space, O(n) time
將新的點儲存在以前每個老的結(jié)點之后眷蜈，如：
0->0'->1->1'->2->2'->NULL
最后再用一次循環(huán)拆開。
總共三個循環(huán)：
第一次將新的節(jié)點添加到老List中去参萄，第二次循環(huán)將新節(jié)點的random指向?qū)男鹿?jié)點驮履，第三次講List拆開，最后返回新的節(jié)點第一個（用dummy node記錄）苗桂。
Tips:
在進行DFS的時候，umordered_map需要用引用傳遞告组，不然內(nèi)存超出限制煤伟。并且要先于下一步dfs之前把節(jié)點添加到其中，不然時間超出限制。
完整代碼：
DFS：
`
RandomListNode *copyRandomList(RandomListNode head)
{
unordered_map <int, RandomListNode> um;
if(head == NULL)
return NULL;
return dfs(head, um);
}
RandomListNode *dfs(RandomListNode node,
unordered_map<int, RandomListNode> &um)
{
if(node == NULL)
return NULL;
if(um.find(node->label) != um.end())
return um[node->label];
RandomListNode *temp = new RandomListNode(node->label);
um[temp->label] = temp;
temp->random = dfs(node->random, um);
temp->next = dfs(node->next, um);
return temp;
}
O(1) Space：
RandomListNode *copyRandomList(RandomListNode *head)
{
if(head == NULL)
return NULL;
RandomListNode * dummy = new RandomListNode(0);
dummy->next = head;
//get nodes
while(head != NULL)
{
RandomListNode *temp = new RandomListNode(head->label);
temp->next = head->next;
head->next = temp;
head = head->next->next;
}
//get randoms point
head = dummy->next;
while(head != NULL)
{
if(head->random != NULL)
head->next->random = head->random->next;
head = head->next->next;
}
//complete list
dummy = dummy->next->next;
head = dummy;
while(head->next != NULL)
{
head->next = head->next->next;
head = head->next;
}
return dummy;
}
`
