Back to solutions

Copy List with Random Pointer

MediumLinked List

Deep copy a linked list where each node has an extra random pointer to any node or null.

Open problem
Constraints
  • 0 <= n <= 1000
  • random points to a node in the list or null

Hash map original to copy

Time O(n)Space O(n)

First pass clones each node into a map keyed by the original. Second pass wires next and random pointers of each clone using the map.

#include <bits/stdc++.h>
using namespace std;

struct Node { int val; Node* next; Node* random; };

Node* copyRandomList(Node* head) {
    unordered_map<Node*, Node*> clone;
    for (Node* p = head; p; p = p->next)
        clone[p] = new Node{p->val, nullptr, nullptr};
    for (Node* p = head; p; p = p->next) {
        clone[p]->next = clone[p->next];
        clone[p]->random = clone[p->random];
    }
    return clone[head];
}