Copy List with Random Pointer
Copy List with Random Pointer is a medium linked list problem solved with the miscellaneous pattern.
The best approach, optimal (interleave copies in the list), runs in O(n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from hash map from original to copy up.
Problem
Each node of a linked list has a next pointer and a random pointer that can point to any node in the list or be null. Build a deep copy: brand-new nodes whose next and random pointers mirror the original structure. No pointer in the copy may point into the original list.
Examples
Example 1
- Input
head = [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]]- Output
a deep copy with the same structure- Why
- Each pair is [value, index that random points to].
Example 2
- Input
head = []- Output
[]
Constraints
- The list has
0to1000nodes. - random can point to any node or be null.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 4 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Hash map from original to copy | O(n) | O(n) |
| Optimal (interleave copies in the list) | O(n) | O(1) |
1Hash map from original to copy
O(n)O(n)First pass: create a copy of every node and store original → copy. Second pass: set each copy's next and random using the map.
- map.put(node, new Node(node.val)) for every node.
- copy.next = map.get(node.next); copy.random = map.get(node.random).
class Solution {
public Node copyRandomList(Node head) {
Map<Node, Node> map = new HashMap<>();
for (Node p = head; p != null; p = p.next) map.put(p, new Node(p.val));
for (Node p = head; p != null; p = p.next) {
map.get(p).next = map.get(p.next);
map.get(p).random = map.get(p.random);
}
return map.get(head);
}
}class Solution:
def copyRandomList(self, head: Optional[Node]) -> Optional[Node]:
map = {}
p = head
while p:
map[p] = Node(p.val)
p = p.next
p = head
while p:
map[p].next = map.get(p.next)
map[p].random = map.get(p.random)
p = p.next
return map.get(head)class Solution {
public:
Node* copyRandomList(Node* head) {
unordered_map<Node*, Node*> map;
map[nullptr] = nullptr;
for (Node* p = head; p != nullptr; p = p->next) map[p] = new Node(p->val);
for (Node* p = head; p != nullptr; p = p->next) {
map[p]->next = map[p->next];
map[p]->random = map[p->random];
}
return map[head];
}
};function copyRandomList(head) {
const map = new Map();
for (let p = head; p !== null; p = p.next) map.set(p, new Node(p.val));
for (let p = head; p !== null; p = p.next) {
map.get(p).next = map.get(p.next) ?? null;
map.get(p).random = map.get(p.random) ?? null;
}
return map.get(head) ?? null;
}2Optimal (interleave copies in the list)
O(n)O(1)No map; only the copies themselves, which are the output.Insert each copy right after its original: A → A' → B → B'. Then A'.random = A.random.next. Finally split the two interleaved lists apart.
- Pass 1: insert copies after each node.
- Pass 2: copy.random = orig.random == null ? null : orig.random.next.
- Pass 3: restore originals and link the copies together.
class Solution {
public Node copyRandomList(Node head) {
for (Node p = head; p != null; p = p.next.next) {
Node c = new Node(p.val);
c.next = p.next;
p.next = c;
}
for (Node p = head; p != null; p = p.next.next)
if (p.random != null) p.next.random = p.random.next;
Node dummy = new Node(0), tail = dummy;
for (Node p = head; p != null; p = p.next) {
Node c = p.next;
p.next = c.next;
tail.next = c;
tail = c;
}
return dummy.next;
}
}class Solution:
def copyRandomList(self, head: Optional[Node]) -> Optional[Node]:
p = head
while p:
c = Node(p.val)
c.next = p.next
p.next = c
p = p.next.next
p = head
while p:
if p.random:
p.next.random = p.random.next
p = p.next.next
dummy = Node(0)
tail = dummy
p = head
while p:
c = p.next
p.next = c.next
tail.next = c
tail = c
p = p.next
return dummy.nextclass Solution {
public:
Node* copyRandomList(Node* head) {
for (Node* p = head; p != nullptr; p = p->next->next) {
Node* c = new Node(p->val);
c->next = p->next;
p->next = c;
}
for (Node* p = head; p != nullptr; p = p->next->next)
if (p->random != nullptr) p->next->random = p->random->next;
Node* dummy = new Node(0);
Node* tail = dummy;
for (Node* p = head; p != nullptr; p = p->next) {
Node* c = p->next;
p->next = c->next;
tail->next = c;
tail = c;
}
return dummy->next;
}
};function copyRandomList(head) {
for (let p = head; p !== null; p = p.next.next) {
const c = new Node(p.val);
c.next = p.next;
p.next = c;
}
for (let p = head; p !== null; p = p.next.next)
if (p.random !== null) p.next.random = p.random.next;
const dummy = new Node(0);
let tail = dummy;
for (let p = head; p !== null; p = p.next) {
const c = p.next;
p.next = c.next;
tail.next = c;
tail = c;
}
return dummy.next;
}Edge cases to test
- random points to itself
- random is null
- Empty list
Hints
Hint 1
You need a mapping from each original node to its copy. Can the copy live right after the original in the list itself?
FAQ
What is the best time complexity for Copy List with Random Pointer?
Optimal (interleave copies in the list) runs in O(n) time and O(1) extra space.
Which pattern does Copy List with Random Pointer use?
It is a linked list problem that uses the miscellaneous pattern. Other problems with the same pattern: Delete Node in a Linked List, Intersection of Two Linked Lists, Partition List.
Is there a brute force solution for Copy List with Random Pointer?
Yes. Hash map from original to copy takes O(n) time and O(n) space. First pass: create a copy of every node and store original → copy.
Which edge cases should I test for Copy List with Random Pointer?
random points to itself; random is null; Empty list.