The challenge
Deep-copy an acyclic next chain whose nodes also have arbitrary random pointers.
Each random pointer is null or refers to a node in the same next chain. The input remains unchanged.
Example
A random link from original A to original C becomes copy A → copy C, never a link into the original.
Use the walkthrough below to inspect the input and each state change.
See Copy random pointers, step by step
Follow the pointers. Watch each link change.
A1Inspect node links
| Node | Value | Next | Random |
|---|---|---|---|
| A1 | 7 | A2 | null |
| A2 | 13 | A3 | A1 |
| A3 | 11 | A4 | A4 |
| A4 | 10 | null | A2 |
Read the input
IDs label node objects. Equal values can belong to different nodes. Solid arrows are next links; dashed arrows are random links.
Start from the input head pointers.View original input
A: 7 (A1) → 13 (A2) → 11 (A3) → 10 (A4); parameters: {"random":[null,0,3,1]}
Parameter indices are zero-based, except n from the end, which is one-based. Node IDs remain fixed when links change.
Put it into code
Allocate every clone first so even forward and self random links already have a destination.
Node stores val and next; the random-pointer lesson adds random. C++ uses C++17 or later.
class Node:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
self.random = None
def copy_random(head):
copies = {None: None}
curr = head
while curr:
copies[curr] = Node(curr.val)
curr = curr.next
curr = head
while curr:
copies[curr].next = copies[curr.next]
copies[curr].random = copies[curr.random]
curr = curr.next
return copies[head]
#include <cstddef>
#include <unordered_map>
struct Node {
int val;
Node* next;
Node* random = nullptr;
Node(int value = 0, Node* link = nullptr)
: val(value), next(link) {}
};
Node* copy_random(Node* head) {
std::unordered_map<Node*, Node*> copies;
copies[nullptr] = nullptr;
for (Node* curr = head; curr; curr = curr->next)
copies[curr] = new Node(curr->val);
for (Node* curr = head; curr; curr = curr->next) {
copies[curr]->next = copies[curr->next];
copies[curr]->random = copies[curr->random];
}
return copies[head];
}