Copy List with Random Pointer — Editorial

Opening the reading…

Intuitiona deep copy needs identity, not just values

The next links describe a simple order, but random links can jump to any node, including a node that has not been copied yet. Copying a value is therefore not enough: for every original node, you need to know exactly which new node represents it. That correspondence is the central piece of the solution.

Create every copied node first and store original node -> copied node in a hash map. Once every identity is known, a second pass can assign each copied next and random pointer by looking up the corresponding original target. The copied list never points back into the original list, so it is a genuine deep copy.

The harness uses rows rather than node objects. A row's randomIndex is only an input encoding of a pointer. The solution first reconstructs real nodes, clones those nodes, and finally walks the copied next chain to assign each copied random pointer its new zero-based index. This last walk also guarantees that the returned order follows next, not random.

The map preserves node identity while the copied pointers remain independent.

Approach

Build the original linked list from the rows, connecting consecutive nodes with next and translating each nonnegative randomIndex into a pointer; this gives the clone logic the same pointer structure described by the input.

Walk the original next chain once and allocate one new node per original node, recording copied[original] = copy; without this complete map, a random pointer may refer to a node that has not been created yet.

Walk the original chain a second time and set each copied node's next pointer from copied[node->next] and random pointer from copied[node->random]; null targets stay null through explicit checks.

Serialize the copied chain by recording its nodes in next order and mapping each copied node to its output index; pointer addresses cannot be returned, so every random pointer must become an index again.

For each copied node, emit its value and either the index of its random target or -1; using the copied index map ensures the returned rows describe the new list rather than the original one.

Return the serialized rows, including an empty result when the input has no nodes; the empty case must not attempt to read a head node.

Complexitythe map buys clarity and linear work

MEASURE	BOUND	WHY
Time	O(n)	Building, cloning, and serializing each walk through the next chain visits every node a constant number of times. Each random assignment and hash-map lookup is constant average time, so no node causes a scan of the list.
Space	O(n) extra	The original and copied node objects, the node map, and the serialization index map each hold O(n) entries; the returned rows are required output and are excluded from extra space. The bound remains O(n) for every input shape because next always forms one linear chain, regardless of where random points.

Here n is the number of rows, and therefore the number of nodes in the reconstructed list.

Annotated solutionC++ · two passes with an identity map

CPPReconstruct the list, clone by identity in two passes, and serialize the copy.

#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
    struct Node {
        int value;
        Node* next;
        Node* random;

        Node(int value) : value(value), next(nullptr), random(nullptr) {}
    };

    Node* build(const vector<vector<int>>& rows) {
        if (rows.empty()) return nullptr;

        vector<Node*> nodes;
        nodes.reserve(rows.size());
        for (const auto& row : rows) {
            nodes.push_back(new Node(row[0]));
        }

        for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
            if (i + 1 < static_cast<int>(nodes.size())) {
                nodes[i]->next = nodes[i + 1];
            }
            int randomIndex = rows[i][1];
            if (randomIndex != -1) {
                nodes[i]->random = nodes[randomIndex];
            }
        }
        return nodes[0];
    }

    Node* clone(Node* head) {
        unordered_map<Node*, Node*> copied;

        for (Node* node = head; node != nullptr; node = node->next) {
            copied[node] = new Node(node->value);
        }

        for (Node* node = head; node != nullptr; node = node->next) {
            Node* copy = copied[node];
            copy->next = node->next == nullptr ? nullptr : copied[node->next];
            copy->random = node->random == nullptr ? nullptr : copied[node->random];
        }

        return head == nullptr ? nullptr : copied[head];
    }

    vector<vector<int>> serialize(Node* head) {
        vector<Node*> order;
        unordered_map<Node*, int> index;

        for (Node* node = head; node != nullptr; node = node->next) {
            index[node] = static_cast<int>(order.size());
            order.push_back(node);
        }

        vector<vector<int>> result;
        result.reserve(order.size());
        for (Node* node : order) {
            int randomIndex = node->random == nullptr ? -1 : index[node->random];
            result.push_back({node->value, randomIndex});
        }
        return result;
    }

public:
    vector<vector<int>> copyRandomList(vector<vector<int>>& nodes) {
        Node* original = build(nodes);
        Node* copied = clone(original);
        return serialize(copied);
    }
};

The first cloning pass deliberately sets only values and map entries. The second pass is where both pointers are wired. That separation is the insight: copied[node->random] is guaranteed to exist because the first pass has already created every node, including targets that appear later in the next chain.

The interleaved alternativean O(1) auxiliary-space variant when pointer manipulation is worth it

You can avoid the hash map by inserting each copy immediately after its original: original -> copy -> next. Then an original random target's copy is always target->next. After assigning random links, split the interleaved chain into the original and copied chains. This is an optimization in auxiliary space, not in time: it remains linear, but it temporarily mutates the original list and is easier to get wrong.

CPPInterleave copies with originals, wire random pointers through next, then restore both chains.

#include <vector>

using namespace std;

class Solution {
    struct Node {
        int value;
        Node* next;
        Node* random;

        Node(int value) : value(value), next(nullptr), random(nullptr) {}
    };

    Node* build(const vector<vector<int>>& rows) {
        if (rows.empty()) return nullptr;

        vector<Node*> nodes;
        nodes.reserve(rows.size());
        for (const auto& row : rows) {
            nodes.push_back(new Node(row[0]));
        }
        for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
            if (i + 1 < static_cast<int>(nodes.size())) {
                nodes[i]->next = nodes[i + 1];
            }
            if (rows[i][1] != -1) {
                nodes[i]->random = nodes[rows[i][1]];
            }
        }
        return nodes[0];
    }

    Node* clone(Node* head) {
        if (head == nullptr) return nullptr;

        for (Node* node = head; node != nullptr;) {
            Node* copy = new Node(node->value);
            copy->next = node->next;
            node->next = copy;
            node = copy->next;
        }

        for (Node* node = head; node != nullptr; node = node->next->next) {
            Node* copy = node->next;
            copy->random = node->random == nullptr ? nullptr : node->random->next;
        }

        Node* copiedHead = head->next;
        for (Node* node = head; node != nullptr;) {
            Node* copy = node->next;
            node->next = copy->next;
            copy->next = copy->next == nullptr ? nullptr : copy->next->next;
            node = node->next;
        }
        return copiedHead;
    }

    vector<vector<int>> serialize(Node* head) {
        vector<Node*> order;
        vector<vector<int>> result;
        for (Node* node = head; node != nullptr; node = node->next) {
            order.push_back(node);
        }
        for (int i = 0; i < static_cast<int>(order.size()); ++i) {
            int randomIndex = -1;
            if (order[i]->random != nullptr) {
                for (int j = 0; j < static_cast<int>(order.size()); ++j) {
                    if (order[j] == order[i]->random) {
                        randomIndex = j;
                        break;
                    }
                }
            }
            result.push_back({order[i]->value, randomIndex});
        }
        return result;
    }

public:
    vector<vector<int>> copyRandomList(vector<vector<int>>& nodes) {
        Node* original = build(nodes);
        Node* copied = clone(original);
        return serialize(copied);
    }
};

The interleaving clone uses O(1) auxiliary pointer storage for the cloning phase, while the node objects themselves still require linear storage and the returned serialization is excluded from the extra-space count. In this serialized harness, the shown serializer performs a simple index search, so the complete wrapper can take O(n squared); with an index map, serialization returns to O(n).