Log inSign up
mediumLeetCodeNot Started

Copy List with Random Pointer

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Linked List
Solve on LeetCode
Lesson

Problem Statement

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where: - val: an integer representing Node.val - random_index: the index of the node (0-indexed) that the random pointer points to, or null if it does not point to any node.

Your code will only be given the head of the original linked list.

Example 1 · Standard 5-Node List with Random References:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Explanation: Every node is cloned with both its next and random pointers replicating original relationships.

Example 2 · 2-Node List with Mutual and Self Pointers:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]
Explanation: Node 0 points to node 1; node 1 points to node 1 (self-loop).

Example 3 · Empty List:

Input: head = []
Output: []
Explanation: An empty list returns null.

Constraints:

  • 0 <= n <= 1000
  • -10^4 <= Node.val <= 10^4
  • Node.random is null or is pointing to some node in the linked list.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Differentiate deep cloning from shallow pointer copying.
  • Master the 3-pass Interweaving Pattern to achieve O(1) auxiliary space in graph/pointer problems.
  • Safely decouple merged/interwoven linked lists without corrupting original links.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Linked list with arbitrary secondary pointers (random or arbitrary).
  • Graph or complex object deep cloning where nodes reference forward and backward elements.
  • Follow-up asking for O(1) auxiliary space optimization.

Algorithmic Decision Tree:

  • If extra memory is allowed: Use a Hash Map oldNode -> newNode in two passes.
  • If O(1) auxiliary memory is required: Use the 3-pass Interweaving & Decoupling strategy.

Connected Patterns:

Clone GraphCopy List with Random and Down PointersFlatten a Multilevel Doubly Linked List

1. Brute Force — Index Mapping via Linear Search

Intuition

First duplicate the linear chain using next pointers. Then, for each original node, count how many steps away its random pointer is, and take that many steps in the copied list to assign the random pointer.

Algorithm

  1. Step 1: Traverse the original list and copy all nodes using only next pointers.
  2. Step 2: Store pointers to all original nodes and copied nodes in two indexed arrays.
  3. Step 3: For each original node i, find the index j of its random pointer in the original array.
  4. Step 4: Set copied[i].random = copied[j] (or null if random was null).
  5. Step 5: Return the head of the copied list.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Node {
7public:
8 int val;
9 Node* next;
10 Node* random;
11 Node(int _val) {
12 val = _val;
13 next = nullptr;
14 random = nullptr;
15 }
16};
17
18class Solution {
19public:
20 Node* copyRandomList(Node* head) {
21 if (!head) return nullptr;
22 vector<Node*> orig, cloned;
23 Node* curr = head;
24 while (curr) {
25 orig.push_back(curr);
26 cloned.push_back(new Node(curr->val));
27 curr = curr->next;
28 }
29
30 for (int i = 0; i < orig.size(); i++) {
31 if (i + 1 < orig.size()) cloned[i]->next = cloned[i + 1];
32 if (orig[i]->random) {
33 for (int j = 0; j < orig.size(); j++) {
34 if (orig[i]->random == orig[j]) {
35 cloned[i]->random = cloned[j];
36 break;
37 }
38 }
39 }
40 }
41 return cloned[0];
42 }
43};
44
45int main() {
46 Node* n1 = new Node(1);
47 Node* n2 = new Node(2);
48 n1->next = n2;
49 n1->random = n2;
50 n2->random = n2;
51
52 Solution sol;
53 Node* res = sol.copyRandomList(n1);
54 cout << "Brute Force Copy Head: " << res->val << ", Random: " << res->random->val << endl;
55 return 0;
56}

Time & Space Complexity

  • Time complexity: O(N^2) — For each of the N nodes, finding the index of its random pointer requires an O(N) traversal.
  • Space complexity: O(N) — Requires arrays to store node references for index lookups.

Why Brute Force Doesn't Scale:

O(N2) index search becomes prohibitively slow on lists with 10,000+ nodes.

For a linked list with 1,000,000 nodes, the in-place interweaving method takes ~12ms and consumes zero auxiliary memory, whereas a hash map requires >80MB of hash bucket allocations.

2. Better — Hash Map (Two Passes)

Intuition

Use a hash table to record map[originalNode] = clonedNode. In the second pass, assign map[curr].next = map[curr.next] and map[curr].random = map[curr.random] in O(1) lookup time per node.

Algorithm

  1. Step 1: If head is null, return null.
  2. Step 2: Initialize hash map map.
  3. Step 3: First Pass: Traverse original list, create a copy for each node, and store map[curr] = new Node(curr.val).
  4. Step 4: Second Pass: Traverse again and wire pointers: map[curr].next = map.get(curr.next) and map[curr].random = map.get(curr.random).
  5. Step 5: Return map[head].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <unordered_map>
3
4using namespace std;
5
6class Node {
7public:
8 int val;
9 Node* next;
10 Node* random;
11 Node(int _val) : val(_val), next(nullptr), random(nullptr) {}
12};
13
14class Solution {
15public:
16 Node* copyRandomList(Node* head) {
17 if (!head) return nullptr;
18 unordered_map<Node*, Node*> mp;
19
20 Node* curr = head;
21 while (curr) {
22 mp[curr] = new Node(curr->val);
23 curr = curr->next;
24 }
25
26 curr = head;
27 while (curr) {
28 mp[curr]->next = mp[curr->next];
29 mp[curr]->random = mp[curr->random];
30 curr = curr->next;
31 }
32
33 return mp[head];
34 }
35};
36
37int main() {
38 Node* n1 = new Node(10);
39 Node* n2 = new Node(20);
40 n1->next = n2;
41 n1->random = n2;
42 n2->random = n1;
43
44 Solution sol;
45 Node* res = sol.copyRandomList(n1);
46 cout << "HashMap C++ Output: Node1 val=" << res->val << ", next=" << res->next->val << ", random=" << res->random->val << endl;
47 return 0;
48}

Time & Space Complexity

  • Time complexity: O(N) — Pass 1 and Pass 2 each visit N nodes with O(1) hash map operations.
  • Space complexity: O(N) — Hash map stores mapping of N original nodes to N newly created cloned nodes.

3. Optimal — 3-Pass In-Place Interweaving (O(1) Auxiliary Space)

Intuition

Instead of an external map, we weave each cloned node right next to its original node: A -> A' -> B -> B'. Now, the clone of curr.random is simply curr.random.next! Finally, we separate the interwoven lists.

Algorithm

  1. Step 1: Pass 1 (Interweave): For each node curr, create clone = new Node(curr.val). Insert clone between curr and curr.next. Advance curr = clone.next.
  2. Step 2: Pass 2 (Assign Randoms): For each original node curr, if curr.random exists, set curr.next.random = curr.random.next. Advance curr = curr.next.next.
  3. Step 3: Pass 3 (Decouple & Restore): Separate the interwoven list into the original list and the clone list. Set curr.next = clone.next and clone.next = clone.next ? clone.next.next : null.
  4. Step 4: Return the head of the cloned list (cloneHead).

Copy List with Random Pointer Master Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Each clone is now easily reachable from its original node
Visual state
Values and pointers at this exact step
linked list
chain → A -> A' -> B -> B' -> C -> C'
Node 1
A
Node 2
A'
Node 3
B
Node 4
B'
Node 5
C
Node 6
C'
NULL
Check / comparison
curr.next = clone; clone.next = nextNode
Decision / next transition
Interweaving complete
Why this step matters

Each clone is now easily reachable from its original node.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5class Node {
6public:
7 int val;
8 Node* next;
9 Node* random;
10 Node(int _val) : val(_val), next(nullptr), random(nullptr) {}
11};
12
13class Solution {
14public:
15 Node* copyRandomList(Node* head) {
16 if (!head) return nullptr;
17
18 // Pass 1: Interweave cloned nodes
19 Node* curr = head;
20 while (curr) {
21 Node* clone = new Node(curr->val);
22 clone->next = curr->next;
23 curr->next = clone;
24 curr = clone->next;
25 }
26
27 // Pass 2: Set random pointers for cloned nodes
28 curr = head;
29 while (curr) {
30 if (curr->random) {
31 curr->next->random = curr->random->next;
32 }
33 curr = curr->next->next;
34 }
35
36 // Pass 3: Decouple the lists
37 Node* cloneHead = head->next;
38 curr = head;
39 while (curr) {
40 Node* clone = curr->next;
41 curr->next = clone->next;
42 if (clone->next) {
43 clone->next = clone->next->next;
44 }
45 curr = curr->next;
46 }
47
48 return cloneHead;
49 }
50};
51
52int main() {
53 Node* n1 = new Node(100);
54 Node* n2 = new Node(200);
55 n1->next = n2;
56 n1->random = n2;
57 n2->random = n1;
58
59 Solution sol;
60 Node* result = sol.copyRandomList(n1);
61
62 cout << "Optimal Interweaving Output:" << endl;
63 cout << "Clone Node 1: val=" << result->val << ", random=" << result->random->val << endl;
64 cout << "Clone Node 2: val=" << result->next->val << ", random=" << result->next->random->val << endl;
65 return 0;
66}

Time & Space Complexity

  • Time complexity: O(N) — Three linear scans across N nodes total 3N steps = O(N) time.
  • Space complexity: O(1) auxiliary space (O(N) for output list) — No hash map or extra data structures used; cloned nodes are woven directly between original nodes.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Linear Scan for Random PointersO(N^2)O(N)First copy the singly linked list using next pointers. For every node, find the index of its random node via linear search from the head, then traverse the clone list to link the corresponding clone node.Repeated linear scans to locate random pointer targets.
2.Better — Hash Map (Two-Pass)O(N)O(N)Pass 1: Create all new nodes and store in map[oldNode] = newNode. Pass 2: Connect map[curr].next = map[curr.next] and map[curr].random = map[curr.random].Hash table memory overhead.
3.Optimal — In-Place Interweaving & DecouplingOptimalO(N)O(1) auxiliary spacePass 1: Insert cloned nodes immediately after each original node. Pass 2: Set curr.next.random = curr.random.next. Pass 3: Separate the two lists.Optimal. Every node must be visited.

Common Pitfalls & Crucial Edge Cases

Failing to Restore the Original List

In Pass 3, leaving original list pointers mutated or broken will fail LeetCode verification tests.

Null Pointer on `curr.random.next`

Forgetting to check if (curr.random != null) before accessing curr.random.next.

Shallow Copying

Returning original nodes or allowing clone.random to point to original list nodes.

Combining Pass 2 and Pass 3

Attempting to decouple while assigning random pointers will break subsequent curr.random.next lookups.

Crucial Edge Cases to Validate:

  • Empty List (`head == null`) — Handled immediately by returning null.
  • Single Node with Self-Loop (`node.random == node`) — curr.next.random = curr.random.next correctly resolves to curr.next (itself).
  • All Random Pointers Null — Handles cleanly since if (curr.random) check prevents null pointer dereferencing.
  • Circular Random Chains — Interweaving works regardless of forward/backward random references because all clones are present before Pass 2.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Start with the Hash Map solution: 'I can solve this in O(N) time and O(N) space using a hash table.'
  2. Immediately follow up with: 'We can optimize space to O(1) auxiliary by interweaving cloned nodes directly after each original node.'
  3. Clearly articulate the 3 passes: 'Pass 1: Interweave, Pass 2: Link Randoms, Pass 3: Decouple and restore.'

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the optimal approach require 3 distinct passes instead of doing everything in one pass?

2.In the interweaving approach, how do we access the cloned node corresponding to curr.random?

3.What is the auxiliary space complexity of the interweaving method?

Back to DSA Sheet