Algo: Sweep the list three times.

create a new copy and insert it behind the old node.

update random pointer

split the list into two. One is the orignial list, and the other is the answer.
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
if (head == nullptr)
return head;
RandomListNode * p = head;
while (p != nullptr) {
RandomListNode * copy = new RandomListNode(p>label);
copy>next = p>next;
p>next = copy;
p = copy>next;
}
p = head;
RandomListNode * q = p>next;
while (p != nullptr) {
if (p>random != nullptr) {
q>random = p>random>next;
}
p = q>next;
if (p != nullptr)
q = p>next;
}
RandomListNode * ans = head>next;
p = head;
q = p>next;
while (p != nullptr) {
p>next = q>next;
if (q>next != nullptr)
q>next = q>next>next;
p = p>next;
q = q>next;
}
return ans;
}
};