https://leetcode.com/problems/copy-list-with-random-pointer/

Inefficient

``````class Solution {
public:
Node *copyRandomList(Node *head) {
map<Node *, Node *> mp;

for (Node *c = head; c != nullptr; c = c->next)
mp[c] = new Node(c->val);

for (Node *c = head; c != nullptr; c = c->next) {
mp[c]->next = mp[c->next];
mp[c]->random = mp[c->random];
}

return mp[head];
}
};
``````

Optimised

``````class Solution {
public:
Node *copyRandomList(Node *head) {
Node *iter = head;
Node *front = head;

while (iter != nullptr) {
front = iter->next;

Node *copy = new Node(iter->val);
iter->next = copy;
copy->next = front;

iter = front;
}

iter = head;
while (iter != nullptr) {
if (iter->random != nullptr) {
iter->next->random = iter->random->next;
}
iter = iter->next->next;
}

iter = head;
Node *pseudoHead = new Node(0);
Node *copy = pseudoHead;

while (iter != nullptr) {
front = iter->next->next;

copy->next = iter->next;

iter->next = front;

copy = copy->next;
iter = front;
}

return pseudoHead->next;
}
};
``````