题目链接：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.

这道题的要求是对一个节点具有随机指针的链表进行深拷贝。

和Clone Graph类似的题目，同样是用hash表将链表中节点与深拷贝的对应的节点关联起来。

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution
{
public:
    RandomListNode *copyRandomList(RandomListNode *head)
    {
        if(head == NULL)
            return NULL;
        
        unordered_map<RandomListNode *, RandomListNode *> m;
        m[head] = new RandomListNode(head -> label);
        for(RandomListNode *p = head; p -> next != NULL; p = p -> next)
        {
            m[p -> next] = new RandomListNode(p -> next -> label);
            m[p] -> next = m[p -> next];
        }
        
        for(RandomListNode *p = head; p != NULL; p = p -> next)
            m[p] -> random = m[p -> random];
        
        return m[head];
    }
};