Copy List with Random Pointer solution and explanation
Google
9 more videos on this problem
Copy List with Random Pointer - Linked List - Leetcode 138NeetCode · 10:07 · 218K views
L27. Clone a LinkedList with Next and Random Pointers | Copy List with Random Pointerstake U forward · 33:00 · 196K views
Copy List with Random Pointer | DSA Series by @shradhaKDShradha Khapra · 20:52 · 85K views
Copy List With Random Pointer (LeetCode 138) | Full Solution with animations and 3 step processNikhil Lohia · 21:45 · 16K views
Copy List with Random Pointer | 2 Approaches | Clear Intuition | Dry Run | Microsoft| Leetcode - 138codestorywithMIK · 45:08 · 16K views
Copy List with Random Pointer - Leetcode 138 - Linked Lists (Python)Greg Hogg · 7:44 · 13K views
LeetCode Tutorial 138. Copy List with Random PointerGoodTecher · 19:59 · 7K views
Copy List with Random Pointer | Live Coding with Explanation | Leetcode #138Algorithms Made Easy · 10:37 · 5K views
Deep Copy Linked List with Random Pointers ULTIMATE Guide to Acing Coding Interviews LeetCode 138vanAmsen · 7:13 · 2K views
Leetcode - Copy List with Random Pointer (Python)Timothy H Chang · 9:26 · 2K views
The problem
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 representingNode.valrandom_index: the index of the node (range from0ton-1) that therandompointer points to, ornullif it does not point to any node.
Your code will only be given the head of the original linked list.
Example 1:
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Example 2:
Input: head = [[1,1],[2,1]] Output: [[1,1],[2,1]]
Example 3:
Input: head = [[3,null],[3,0],[3,null]] Output: [[3,null],[3,0],[3,null]]
Constraints:
0 <= n <= 1000-104 <= Node.val <= 104Node.randomisnullor is pointing to some node in the linked list.
Approach overview
Problem Overview: You are given a linked list where each node has two pointers: next and random. The random pointer can point to any node in the list or null. The task is to create a deep copy of this list so that the new list has entirely new nodes but preserves both pointer relationships.
Approach 1: Using Hash Map (O(n) time, O(n) space)
This method builds the cloned list in two passes using a hash table. First, iterate through the original list and create a copy node for each original node. Store the mapping originalNode → clonedNode in the map. In the second pass, assign next and random pointers by performing constant-time lookups in the map. This works because every original node already has its clone stored in the dictionary.
The key insight is that pointer relationships can be reconstructed by translating original references through the map. If node.random points to some node R, then the cloned node’s random pointer simply becomes map[R]. This approach is straightforward, easy to implement, and commonly used in interviews when clarity matters more than space optimization.
Approach 2: Interleaving Nodes (O(n) time, O(1) space)
This approach avoids extra memory by weaving copied nodes directly into the original linked list. During the first pass, insert each cloned node immediately after its original node. The list transforms from A → B → C into A → A' → B → B' → C → C'.
In the second pass, set the random pointers for cloned nodes. Because each copy sits right after its original, the correct target becomes node.random.next. This allows constant-time pointer assignment without a hash table. Finally, perform a third pass to separate the interleaved list into two independent lists: the original and the deep copy.
The main insight is that adjacency between original and cloned nodes eliminates the need for external mapping. Every reference can be resolved using local pointer relationships created during the interleaving step.
Recommended for interviews: Both solutions run in O(n) time. The hash map approach demonstrates clear reasoning about pointer mapping and is often the easiest way to reach a correct solution quickly. The interleaving technique is the optimal solution because it reduces extra memory to O(1). Interviewers frequently expect candidates to start with the hash map idea and then optimize using pointer manipulation within the linked list.
Approach 1: Approach 1: Using Hash Map
This approach involves using a hash map to build a one-to-one mapping from the original list nodes to the copied list nodes. The algorithm consists of the following main steps:
- Create the new nodes and build the
nextchain of the deep copy, while storing the mapping of original nodes to copied nodes in a hash map. - Use the hash map to set up the
randompointers in the copied list by referring back to the original nodes'randompointers.
class Node:
def __init__(self, val=0, next=None, random=None):
self.val = val
self.next = next
self.random = random
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
if not head:
return None
# Create a dictionary to map old nodes to new nodes
old_to_new = {}
# First pass: copy nodes and store mapping in hash map
current = head
while current:
clone = Node(current.val)
old_to_new[current] = clone
current = current.next
# Second pass: assign next and random pointers
current = head
while current:
if current.next:
old_to_new[current].next = old_to_new[current.next]
if current.random:
old_to_new[current].random = old_to_new[current.random]
current = current.next
return old_to_new[head]The solution uses a two-pass algorithm:
- First Pass: It traverses the original list and creates a deep copy of each node, storing each original node's copy in a dictionary with the original node as the key. The copy is only the node without the exact
nextandrandomlinkages. - Second Pass: It uses the same traversal through the original list, this time establishing the correct
nextandrandompointers for the copied nodes. These are set using the previously built dictionary.
Time Complexity: O(n), where n is the number of nodes in the linked list, because we pass through the list twice.
Space Complexity: O(n) due to the use of a dictionary that stores mappings for each node.
Approach 2: Approach 2: Interleaving Nodes
This approach involves interleaving the cloned nodes with original ones in the same list. The three main steps include:
- Interleave nodes: Create a copy of each node and insert it right after the original one in the original list.
- Assign random pointers for the cloned nodes using interleaving technique.
- Separate the two lists by restoring the original list and forming the cloned list.
function Node(val, next, random) {
this.val = val;
this.next = next;
this.random = random;
};
function copyRandomList(head) {
if (!head) return null;
let current = head;
// First pass: Make copy just after each original node
while (current) {
const copy = new Node(current.val, current.next, null);
const nextOriginal = current.next;
current.next = copy;
copy.next = nextOriginal;
current = nextOriginal;
}
// Second pass: Set correct random pointers
current = head;
while (current) {
if (current.random) {
current.next.random = current.random.next;
}
current = current.next.next;
}
// Third pass: Restore original list, separate out the copied list
let dummy = new Node(0);
let copyCurrent = dummy;
current = head;
while (current) {
const copy = current.next;
copyCurrent.next = copy;
copyCurrent = copy;
current.next = copy.next;
current = current.next;
}
return dummy.next;
}The solution works in three main phases:
- Node Interleaving: A copy of each node is generated in the list itself immediately following the original node. Each original node's
nextpointer is redirected to its clone, and the clone points to the following original node. - Assign Random Pointers: We configure the random pointers for the cloned nodes, which can be achieved because each original node directly links to its clone.
- Separate Lists: Finally, extract the cloned list by correcting the
nextpointers to point to the original list and cloned list separately.
Time Complexity: O(n) as we traverse the list three times independently.
Space Complexity: O(1) as we only use a few additional pointers and no extra data structures.
Approach 3: Hash Map Traversal
This approach involves using a hash map to keep track of the relationship between the original nodes and their corresponding nodes in the copied list. First, traverse the original linked list to create a copy of each node, while storing the mapping from original nodes to copied nodes. In the second pass, assign the 'next' and 'random' pointers in the copied list based on this mapping.
class Node:
def __init__(self, val = 0, next = None, random = None):
self.val = val
self.next = next
self.random = random
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
if not head:
return None
node_map = {}
current = head
# Step 1: Create a copy of each node and store the mapping
while current:
node_map[current] = Node(current.val)
current = current.next
# Step 2: Assign the next and random pointers of the copied nodes
current = head
while current:
node_map[current].next = node_map.get(current.next)
node_map[current].random = node_map.get(current.random)
current = current.next
return node_map[head]import java.util.HashMap;
import java.util.Map;
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
class Solution {
public Node copyRandomList(Node head) {
if (head == null) return null;
Map<Node, Node> nodeMap = new HashMap<>();
Node current = head;
// Step 1: Populate the hash map with original and new node pairs
while (current != null) {
nodeMap.put(current, new Node(current.val));
current = current.next;
}
// Step 2: Assign the next and random pointers
current = head;
while (current != null) {
nodeMap.get(current).next = nodeMap.get(current.next);
nodeMap.get(current).random = nodeMap.get(current.random);
current = current.next;
}
return nodeMap.get(head);
}
}#include <unordered_map>
using namespace std;
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) : val(_val), next(NULL), random(NULL) {}
};
class Solution {
public:
Node* copyRandomList(Node* head) {
if (!head) return nullptr;
unordered_map<Node*, Node*> nodeMap;
Node* current = head;
// Step 1: Create a mapping from original nodes to their copies
while (current) {
nodeMap[current] = new Node(current->val);
current = current->next;
}
// Step 2: Assign next and random pointers
current = head;
while (current) {
nodeMap[current]->next = nodeMap[current->next];
nodeMap[current]->random = nodeMap[current->random];
current = current->next;
}
return nodeMap[head];
}
};function Node(val, next, random) {
this.val = val;
this.next = next;
this.random = random;
};
var copyRandomList = function(head) {
if(!head) return null;
const nodeMap = new Map();
let current = head;
// Step 1: Clone each node and store in the map
while (current) {
nodeMap.set(current, new Node(current.val, null, null));
current = current.next;
}
// Step 2: Assign next and random pointers
current = head;
while (current) {
const copy = nodeMap.get(current);
copy.next = nodeMap.get(current.next) || null;
copy.random = nodeMap.get(current.random) || null;
current = current.next;
}
return nodeMap.get(head);
};#include <stdlib.h>
#include <stdio.h>
#include <unordered_map>
struct Node {
int val;
struct Node* next;
struct Node* random;
};
struct Node* copyRandomList(struct Node* head) {
if (!head) return NULL;
std::unordered_map<struct Node*, struct Node*> nodeMap;
struct Node* current = head;
// Step 1: Create a mapping from original nodes to their copies
while (current) {
nodeMap[current] = (struct Node*)malloc(sizeof(struct Node));
nodeMap[current]->val = current->val;
nodeMap[current]->next = NULL;
nodeMap[current]->random = NULL;
current = current->next;
}
// Step 2: Assign next and random pointers
current = head;
while (current) {
nodeMap[current]->next = current->next ? nodeMap[current->next] : NULL;
nodeMap[current]->random = current->random ? nodeMap[current->random] : NULL;
current = current->next;
}
return nodeMap[head];
}using System.Collections.Generic;
public class Node {
public int val;
public Node next;
public Node random;
public Node(int _val) {
val = _val;
next = null;
random = null;
}
}
public class Solution {
public Node CopyRandomList(Node head) {
if (head == null) return null;
Dictionary<Node, Node> nodeMap = new Dictionary<Node, Node>();
Node current = head;
// Step 1: Create mapping from original nodes to their copies
while (current != null) {
nodeMap[current] = new Node(current.val);
current = current.next;
}
// Step 2: Assign next and random pointers for the copied nodes
current = head;
while (current != null) {
nodeMap[current].next = current.next != null ? nodeMap[current.next] : null;
nodeMap[current].random = current.random != null ? nodeMap[current.random] : null;
current = current.next;
}
return nodeMap[head];
}
}In this Python solution, we maintain a dictionary that maps each original node to its copy. We first create all node copies, and in the second pass, set up the 'next' and 'random' pointers based on this mapping.
Time Complexity: O(n), where n is the number of nodes in the list.
Space Complexity: O(n) for maintaining the node_map dictionary.
Approach 4: Interleaving Method
This approach involves interleaving the copied nodes with the original nodes in the list. By placing each copied node immediately after its original node, the 'random' pointers can be easily assigned by looking at the 'random' pointers of the original nodes. Finally, the original and copied nodes are separated to complete the process.
class Node:
def __init__(self, val=0, next=None, random=None):
self.val = val
self.next = next
self.random = random
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
if not head:
return None
current = head
# Step 1: Insert copy nodes after each original node
while current:
next_node = current.next
copy = Node(current.val)
current.next = copy
copy.next = next_node
current = next_node
# Step 2: Assign random pointers to the copied nodes
current = head
while current:
if current.random:
current.next.random = current.random.next
current = current.next.next
# Step 3: Unweave the linked list to get the original and copy
pseudo_head = Node(0)
copy_current = pseudo_head
current = head
while current:
next_node = current.next.next
copy = current.next
copy_current.next = copy
copy_current = copy
current.next = next_node
current = next_node
return pseudo_head.nextclass Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
class Solution {
public Node copyRandomList(Node head) {
if (head == null) return null;
Node current = head;
// Step 1: Duplicate nodes and interleave them with the original nodes
while (current != null) {
Node copy = new Node(current.val);
copy.next = current.next;
current.next = copy;
current = copy.next;
}
// Step 2: Set random pointers for the copied nodes
current = head;
while (current != null) {
if (current.random != null) {
current.next.random = current.random.next;
}
current = current.next.next;
}
// Step 3: Split from woven state to separate lists
Node pseudoHead = new Node(0);
Node copy = pseudoHead;
current = head;
while (current != null) {
Node nextOriginal = current.next.next;
copy.next = current.next;
copy = copy.next;
current.next = nextOriginal;
current = nextOriginal;
}
return pseudoHead.next;
}
}class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) : val(_val), next(NULL), random(NULL) {}
};
class Solution {
public:
Node* copyRandomList(Node* head) {
if (!head) return nullptr;
Node* current = head;
// Step 1: Duplicate nodes interleaved
while (current) {
Node* copy = new Node(current->val);
copy->next = current->next;
current->next = copy;
current = copy->next;
}
// Step 2: Assign random pointers to the copied nodes
current = head;
while (current) {
current->next->random = current->random ? current->random->next : nullptr;
current = current->next->next;
}
// Step 3: Detach the duplicated list from the original
Node* copyHead = head->next;
Node* copyCurrent = copyHead;
current = head;
while (current) {
current->next = current->next->next;
copyCurrent->next = copyCurrent->next ? copyCurrent->next->next : nullptr;
current = current->next;
copyCurrent = copyCurrent->next;
}
return copyHead;
}
};function Node(val, next, random) {
this.val = val;
this.next = next;
this.random = random;
};
var copyRandomList = function(head) {
if(!head) return null;
let current = head;
// Step 1: Weave copied nodes with original nodes
while (current) {
const copy = new Node(current.val);
copy.next = current.next;
current.next = copy;
current = copy.next;
}
// Step 2: Assign random pointers for copies
current = head;
while (current) {
if (current.random) {
current.next.random = current.random.next;
}
current = current.next.next;
}
// Step 3: Separate the intertwined linked list
const dummy = new Node(0);
let copyIter = dummy;
current = head;
while (current) {
const nextOriginal = current.next.next;
const copy = current.next;
copyIter.next = copy;
copyIter = copy;
current.next = nextOriginal;
current = nextOriginal;
}
return dummy.next;
};#include <stdlib.h>
#include <stdio.h>
struct Node {
int val;
struct Node* next;
struct Node* random;
};
struct Node* copyRandomList(struct Node* head) {
if (!head) return NULL;
struct Node* current = head;
// Step 1: Interleave the list with copied nodes
while (current) {
struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
copy->val = current->val;
copy->next = current->next;
copy->random = NULL;
current->next = copy;
current = copy->next;
}
// Step 2: Set the random pointers
current = head;
while (current) {
if (current->random) {
current->next->random = current->random->next;
}
current = current->next->next;
}
// Step 3: Separate the original and copied nodes
struct Node* dummy = (struct Node*)malloc(sizeof(struct Node));
struct Node* copy;
struct Node* copy_iter = dummy;
current = head;
while (current) {
copy = current->next;
copy_iter->next = copy;
copy_iter = copy;
current->next = copy->next;
current = current->next;
}
return dummy->next;
}public class Node {
public int val;
public Node next;
public Node random;
public Node(int _val) {
val = _val;
next = null;
random = null;
}
}
public class Solution {
public Node CopyRandomList(Node head) {
if (head == null) return null;
Node current = head;
// Step 1: Clone and interleave nodes
while (current != null) {
Node copy = new Node(current.val);
copy.next = current.next;
current.next = copy;
current = copy.next;
}
// Step 2: Establish random pointers
current = head;
while (current != null) {
if (current.random != null) {
current.next.random = current.random.next;
}
current = current.next.next;
}
// Step 3: Unweave the lists
Node pseudoHead = new Node(0);
Node copyIter = pseudoHead;
current = head;
while (current != null) {
Node nextOrignal = current.next.next;
Node copy = current.next;
copyIter.next = copy;
copyIter = copy;
current.next = nextOrignal;
current = nextOrignal;
}
return pseudoHead.next;
}
}This Python implementation uses interleaving with in-place separation by splitting after the establishment of linked and random pointers, ensuring each new node aligns with the replacement of 'next' and 'random' accurately, which ensures precise separation once interleaved nodes are detached.
Time Complexity: O(n), traversals and operations finalize through linear progression.
Space Complexity: O(1), embedded function allows for inline node and list transformation.
Approach 5: Hash Table
We can define a dummy head node dummy and use a pointer tail to point to the dummy head node. Then, we traverse the linked list, copying each node and storing the mapping between each node and its copy in a hash table d, while also connecting the next pointers of the copied nodes.
Next, we traverse the linked list again and use the mappings stored in the hash table to connect the random pointers of the copied nodes.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the linked list.
/**
* Definition for _Node.
* class _Node {
* val: number
* next: _Node | null
* random: _Node | null
*
* constructor(val?: number, next?: _Node, random?: _Node) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* this.random = (random===undefined ? null : random)
* }
* }
*/
function copyRandomList(head: _Node | null): _Node | null {
const d: Map<_Node, _Node> = new Map();
const dummy = new _Node();
let tail = dummy;
for (let cur = head; cur; cur = cur.next) {
const node = new _Node(cur.val);
tail.next = node;
tail = node;
d.set(cur, node);
}
for (let cur = head; cur; cur = cur.next) {
d.get(cur)!.random = cur.random ? d.get(cur.random)! : null;
}
return dummy.next;
}/**
* Definition for a Node.
* type Node struct {
* Val int
* Next *Node
* Random *Node
* }
*/
func copyRandomList(head *Node) *Node {
dummy := &Node{}
tail := dummy
d := map[*Node]*Node{}
for cur := head; cur != nil; cur = cur.Next {
node := &Node{Val: cur.Val}
d[cur] = node
tail.Next = node
tail = node
}
for cur := head; cur != nil; cur = cur.Next {
if cur.Random != nil {
d[cur].Random = d[cur.Random]
}
}
return dummy.Next
}Approach 6: Simulation (Space Optimization)
In Solution 1, we used an additional hash table to store the mapping between the original nodes and the copied nodes. We can also achieve this without using extra space, as follows:
- Traverse the original linked list, and for each node, create a new node and insert it between the original node and the original node's next node.
- Traverse the linked list again, and set the
randompointer of the new node based on therandompointer of the original node. - Finally, split the linked list into the original linked list and the copied linked list.
The time complexity is O(n), where n is the length of the linked list. Ignoring the space occupied by the answer linked list, the space complexity is O(1).
/**
* Definition for _Node.
* class _Node {
* val: number
* next: _Node | null
* random: _Node | null
*
* constructor(val?: number, next?: _Node, random?: _Node) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* this.random = (random===undefined ? null : random)
* }
* }
*/
function copyRandomList(head: _Node | null): _Node | null {
if (head === null) {
return null;
}
let cur = head;
while (cur !== null) {
const node = new _Node(cur.val);
node.next = cur.next;
cur.next = node;
cur = node.next;
}
cur = head;
while (cur !== null) {
cur.next.random = cur.random === null ? null : cur.random.next;
cur = cur.next.next;
}
cur = head;
const ans = head.next;
while (cur.next !== null) {
const node = cur.next;
cur.next = node.next;
cur = node;
}
return ans;
}/**
* Definition for a Node.
* type Node struct {
* Val int
* Next *Node
* Random *Node
* }
*/
func copyRandomList(head *Node) *Node {
if head == nil {
return nil
}
for cur := head; cur != nil; {
node := &Node{cur.Val, cur.Next, nil}
cur.Next = node
cur = node.Next
}
for cur := head; cur != nil; cur = cur.Next.Next {
if cur.Random != nil {
cur.Next.Random = cur.Random.Next
}
}
ans := head.Next
for cur := head; cur.Next != nil; {
node := cur.Next
cur.Next = node.Next
cur = node
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Using Hash Map | Time Complexity: O(n), where n is the number of nodes in the linked list, because we pass through the list twice. Space Complexity: O(n) due to the use of a dictionary that stores mappings for each node. |
| Approach 2: Interleaving Nodes | Time Complexity: O(n) as we traverse the list three times independently. Space Complexity: O(1) as we only use a few additional pointers and no extra data structures. |
| Hash Map Traversal | Time Complexity: O(n), where |
| Interleaving Method | Time Complexity: O(n), traversals and operations finalize through linear progression. |
| Hash Table | – |
| Simulation (Space Optimization) | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map Mapping | O(n) | O(n) | Best for clarity and quick implementation. Easy to reason about using node-to-node mapping. |
| Interleaving Nodes | O(n) | O(1) | Optimal when minimizing memory usage. Common interview follow-up after the hash map approach. |
Frequently asked questions
Is Copy List with Random Pointer easy or hard?
Copy List with Random Pointer is generally considered a medium difficulty problem. The main challenge is correctly preserving random pointer relationships while creating a deep copy. The hash map solution is straightforward, while the O(1) space interleaving method requires careful pointer manipulation.
Copy List with Random Pointer Python/Java solution
In Python or Java, the common implementation uses a hash map that maps each original node to its cloned node. After creating all nodes, a second traversal assigns next and random pointers using the map. This approach runs in O(n) time and O(n) space and is easy to implement in both languages.
How to solve Copy List with Random Pointer in O(n)?
Traverse the list and either store node mappings in a hash table or interleave copied nodes within the original list. The hash map method reconstructs next and random pointers through constant-time lookups. The interleaving method avoids extra memory by temporarily embedding copied nodes beside originals and deriving random references from nearby pointers.
What is the best approach for Copy List with Random Pointer?
The optimal approach is the interleaving nodes technique, which runs in O(n) time and O(1) extra space. It inserts cloned nodes directly between original nodes, assigns random pointers using local relationships, and then separates the two lists. Many candidates first implement the hash map solution because it is simpler, then optimize to the interleaving approach.
Is Copy List with Random Pointer asked at Google/Amazon/Meta?
Copy List with Random Pointer is a common interview question at large tech companies including Amazon, Google, and Meta. It tests understanding of linked list manipulation, pointer relationships, and deep copy semantics. Candidates are often expected to explain both the hash map approach and the O(1) space optimization.
What data structure is used in Copy List with Random Pointer?
The core data structure is a linked list where each node contains two references: next and random. Many implementations also use a hash table to map original nodes to their copied counterparts. The optimized solution manipulates the linked list structure directly to avoid extra memory.
What is the time complexity of Copy List with Random Pointer?
Both common solutions run in O(n) time where n is the number of nodes in the linked list. Each node is visited a constant number of times while building the copy and assigning pointers. The difference between approaches lies in space usage rather than runtime.