The algorithm needs to scan the list three time, one to copy nodes, one to copy random fields, and the last to reconnect the original list and the new list. The basic idea is to interleave the original list and the new list to facilitate the random field copy. "Interleave" means "old_node1->new_node1->old_node2->new_node_2->..."

class Solution {

public:

RandomListNode *copyRandomList(RandomListNode *head) {

RandomListNode *p1, *p2, *temp, *newHead;

```
if(!head)
{
return NULL;
}
else
{
// generate a new list and interleave it with the original list
p1 = head;
while(p1)
{
p2 = new RandomListNode(p1->label);
temp = p1->next;
p1->next = p2;
p2->next = temp;
p1 = temp;
}
// copy the random fields of the new list
p1 = head;
while(p1)
{
p2 = p1->random;
if(p2)
{
p1->next->random = p2->next;
}
p1 = p1->next->next;
}
// separate the original and new lists
p1 =head;
p2 = newHead = head->next;
while(p2->next)
{
p1->next = p2->next;
p1= p1->next;
p2->next = p1->next;
p2 = p2->next;
}
p1->next = NULL;
return newHead;
}
}
};
```