LINKED LIST › LINKED LIST (PART 1)
Open — the attempt gate is not wired up yet
This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.
Try it yourself first →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.
| 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. |
#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.
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.
#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).