题目地址：
https://oj.leetcode.com/problems/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.
/**
* Definition for singly-linked list with a random pointer.
* struct RandomListNode {
* int label;
* RandomListNode *next, *random;
* RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
* };
*/
方法：
难点在于random指针需要指向一个复制过程中还不存在的结点。解决办法就简单了，先复制完单链表，再处理每个结点的random指针，这样复制random指针时其指向的结点就已经存在了。
为了高效完成这个工作，我们需要建立一个映射，以旧地址为键，新地址为值，方便复制random指针。
全部代码：
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
if (!head)
return NULL;
unordered_map<int,int> dict;
RandomListNode *tmpHead = head;
RandomListNode *resHead = NULL;
RandomListNode *now = NULL;
RandomListNode *nxt = NULL;
resHead = (RandomListNode *)malloc(sizeof(RandomListNode));
dict[(int)head] = (int)resHead;
resHead->label = tmpHead->label;
resHead->next = NULL;
resHead->random = NULL;
now = resHead;
tmpHead = tmpHead->next;
while (tmpHead)
{
nxt = (RandomListNode *)malloc(sizeof(RandomListNode));
nxt->label = tmpHead->label;
nxt->next = NULL;
nxt->random = NULL;
dict[(int)tmpHead] = (int)nxt;
now->next = nxt;
now = nxt;
tmpHead = tmpHead->next;
}
tmpHead = head;
while (tmpHead)
{
now = (RandomListNode *)dict[(int)tmpHead];
if (tmpHead->random != NULL)
now->random = (RandomListNode *)dict[(int)(tmpHead->random)];
tmpHead = tmpHead->next;
}
return resHead;
}
};