At first, I think the connection between the old link list and the new one could be recorded using a hash table, which leads to a space complexity of O(n). The solution below only uses O(1) space.

**Here is the thought:**

Step 1. Copy and insert the node after every node in the original link list;

Step 2. Build up the random connections among the new nodes.

Step 3. Divide the two link list and make the new one independent.

```
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
CopyNodes(head);
ConnectRandomNodes(head);
return ReconnectNodes(head);
}
private:
//Copy a node after every node in the original linklist;
void CopyNodes(RandomListNode *head)
{
RandomListNode* node = head;
while (node){
RandomListNode* copy = new RandomListNode(0);
copy->label = node->label;
copy->next = node->next;
copy->random = NULL;
node->next = copy;
node = copy->next;
}
}
//copy the random link in the original linklist;
void ConnectRandomNodes(RandomListNode *head)
{
RandomListNode *node = head;
while (node){
RandomListNode *copy = node->next;
if(node->random)
copy->random = node->random->next;
node = copy->next;
}
}
//divide the linklist to two linklists
RandomListNode *ReconnectNodes(RandomListNode *head)
{
RandomListNode *CopyHead = NULL, *copy = NULL;
RandomListNode *node = head;
if (node){
CopyHead = node->next;
copy = node->next;
node->next = copy->next;
node = node->next;
}
while (node){
copy->next = node->next;
copy = copy->next;
node->next = copy->next;
node = node->next;
}
return CopyHead;
}
};
```