Copy List With Random Pointer
Copy List With Random Pointer Problem
You are given the head of a linked list of length n, where each node has an extra pointer called random, which can point to any node in the list or be null.
Your task is to create a deep copy of the list, ensuring the new list consists of exactly n nodes with the following:
- Each node should have the same value as the original.
- next pointer in the copied node should correspond to the next pointer of the original.
- random pointer in the copied node should correspond to the random pointer of the original.
Important Facts for Copy List With Random Pointer
Note:
None of the pointers in the new list should refer to nodes in the original list.
Linked list is represented as a list of nodes, where each node is shown as [val, random_index]. Here, random_index refers to the index of the node (0-indexed) the random pointer points to, or null if it points to none.
Return the head of the copied linked list.
Example 1:
Illustration 1:
Input: head = [ [ 3 , null ] , [ 7 , 3 ] , [ 4 , 0 ] , [ 5 , 1 ] ]
Output: [ [ 3 , null ] , [ 7 , 3 ] , [ 4 , 0 ] , [ 5 , 1] ]
Output: [ [ 3 , null ] , [ 7 , 3 ] , [ 4 , 0 ] , [ 5 , 1] ]
Example 2:
Example 2:
Input: head = [ [ 1 , null ] , [ 2 , 2 ] , [ 3 , 2 ] ]
Output: [ [ 1, null] , [ 2 , 2 ] , [ 3 , 2] ]
Output: [ [ 1, null] , [ 2 , 2 ] , [ 3 , 2] ]
Constraints:
- 0 <= n <= 100
- -100 <= Node.val <= 100
- random is null or is pointing to some node in the linked list.
Hints to Solve Copy List With Random Pointer
Hint 1 :
Each node has an additional random pointer that can point to any node in the list.
Unlike the next pointer, the random pointer doesn’t follow a fixed sequence. To create a deep copy, all nodes and pointers must be recreated separately.
Why can’t we build the new list in a single iteration?
Hint 2 :
- When copying nodes, we can’t immediately assign random pointers since they may point to nodes that haven’t been copied yet.
- Possible solution is to create copies of all nodes in one pass while storing the mapping between the original and copied nodes.
- Can you think of a data structure to manage this mapping effectively?
Hint 3 :
- Using a hash map can efficiently map each original node to its copy, allowing quick retrieval in O(1) time.
- In the first pass, create node copies and store them in the map. In the second pass, use the map to assign random pointers to the copied nodes.
Recommendation for Time and Space Complexity (For Copy List With Random Pointer)
Aim for a solution with O(n) time and O(n) space, where n is the length of the list.
There are mainly 5 approach to solve Copy List With Random Pointer problem:
- Hash Map (Recursion)
- Hash Map (Two Pass)
- Hash Map (One Pass)
- Space Optimized – I
- Space Optimized – II
1. Hash Map (Recursion)
Use a hash map to store copies of nodes as you recursively traverse the original list. If a node is visited, fetch its copy from the map; otherwise, create a new copy and continue until the entire list is cloned.
- Time complexity: O(n)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
unordered_map map;
Node* copyRandomList(Node* head) {
if (head == nullptr) return nullptr;
if (map.count(head)) return map[head];
Node* copy = new Node(head->val);
map[head] = copy;
copy->next = copyRandomList(head->next);
copy->random = map[head->random];
return copy;
}
};
Java
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
public class Solution {
HashMap map = new HashMap<>();
public Node copyRandomList(Node head) {
if (head == null) return null;
if (map.containsKey(head)) return map.get(head);
Node copy = new Node(head.val);
map.put(head, copy);
copy.next = copyRandomList(head.next);
copy.random = map.get(head.random);
return copy;
}
}
Python
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def __init__(self):
self.map = {}
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
if head is None:
return None
if head in self.map:
return self.map[head]
copy = Node(head.val)
self.map[head] = copy
copy.next = self.copyRandomList(head.next)
copy.random = self.map.get(head.random)
return copy
JavaScript
// class Node {
// constructor(val, next = null, random = null) {
// this.val = val;
// this.next = next;
// this.random = random;
// }
// }
class Solution {
constructor() {
this.map = new Map();
}
/**
* @param {Node} head
* @return {Node}
*/
copyRandomList(head) {
if (head === null) return null;
if (this.map.has(head)) return this.map.get(head);
const copy = new Node(head.val);
this.map.set(head, copy);
copy.next = this.copyRandomList(head.next);
copy.random = this.map.get(head.random) || null;
return copy;
}
}
2. Hash Map (Two Pass)
In the first pass, traverse the original list and create a copy of each node while storing the mapping in a hash map. In the second pass, assign next and random pointers to the copied nodes using the map.
- Time complexity: O(n)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
/*
// Definition for a Node.
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) {
unordered_map oldToCopy;
oldToCopy[NULL] = NULL;
Node* cur = head;
while (cur != NULL) {
Node* copy = new Node(cur->val);
oldToCopy[cur] = copy;
cur = cur->next;
}
cur = head;
while (cur != NULL) {
Node* copy = oldToCopy[cur];
copy->next = oldToCopy[cur->next];
copy->random = oldToCopy[cur->random];
cur = cur->next;
}
return oldToCopy[head];
}
};
Java
/*
// Definition for a Node.
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) {
Map oldToCopy = new HashMap<>();
oldToCopy.put(null, null);
Node cur = head;
while (cur != null) {
Node copy = new Node(cur.val);
oldToCopy.put(cur, copy);
cur = cur.next;
}
cur = head;
while (cur != null) {
Node copy = oldToCopy.get(cur);
copy.next = oldToCopy.get(cur.next);
copy.random = oldToCopy.get(cur.random);
cur = cur.next;
}
return oldToCopy.get(head);
}
}
Python
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
oldToCopy = {None: None}
cur = head
while cur:
copy = Node(cur.val)
oldToCopy[cur] = copy
cur = cur.next
cur = head
while cur:
copy = oldToCopy[cur]
copy.next = oldToCopy[cur.next]
copy.random = oldToCopy[cur.random]
cur = cur.next
return oldToCopy[head]
JavaScript
// class Node {
// constructor(val, next = null, random = null) {
// this.val = val;
// this.next = next;
// this.random = random;
// }
// }
class Solution {
/**
* @param {Node} head
* @return {Node}
*/
copyRandomList(head) {
const oldToCopy = new Map();
oldToCopy.set(null, null);
let cur = head;
while (cur) {
const copy = new Node(cur.val);
oldToCopy.set(cur, copy);
cur = cur.next;
}
cur = head;
while (cur) {
const copy = oldToCopy.get(cur);
copy.next = oldToCopy.get(cur.next);
copy.random = oldToCopy.get(cur.random);
cur = cur.next;
}
return oldToCopy.get(head);
}
}
3. Hash Map (One Pass)
Traverse the list once and simultaneously create copies of nodes, storing them in a hash map. As you create the copy, assign the next and random pointers directly using the map.
- Time complexity: O(n)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
/*
// Definition for a Node.
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) {
unordered_map oldToCopy;
oldToCopy[nullptr] = nullptr;
Node* cur = head;
while (cur != nullptr) {
if (oldToCopy.find(cur) == oldToCopy.end()) {
oldToCopy[cur] = new Node(0);
}
oldToCopy[cur]->val = cur->val;
if (oldToCopy.find(cur->next) == oldToCopy.end()) {
oldToCopy[cur->next] = new Node(0);
}
oldToCopy[cur]->next = oldToCopy[cur->next];
if (oldToCopy.find(cur->random) == oldToCopy.end()) {
oldToCopy[cur->random] = new Node(0);
}
oldToCopy[cur]->random = oldToCopy[cur->random];
cur = cur->next;
}
return oldToCopy[head];
}
};
Java
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
public class Solution {
public Node copyRandomList(Node head) {
HashMap oldToCopy = new HashMap<>();
oldToCopy.put(null, null);
Node cur = head;
while (cur != null) {
if (!oldToCopy.containsKey(cur)) {
oldToCopy.put(cur, new Node(0));
}
oldToCopy.get(cur).val = cur.val;
if (!oldToCopy.containsKey(cur.next)) {
oldToCopy.put(cur.next, new Node(0));
}
oldToCopy.get(cur).next = oldToCopy.get(cur.next);
if (!oldToCopy.containsKey(cur.random)) {
oldToCopy.put(cur.random, new Node(0));
}
oldToCopy.get(cur).random = oldToCopy.get(cur.random);
cur = cur.next;
}
return oldToCopy.get(head);
}
}
Python
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
oldToCopy = collections.defaultdict(lambda: Node(0))
oldToCopy[None] = None
cur = head
while cur:
oldToCopy[cur].val = cur.val
oldToCopy[cur].next = oldToCopy[cur.next]
oldToCopy[cur].random = oldToCopy[cur.random]
cur = cur.next
return oldToCopy[head]JavaScript
// class Node {
// constructor(val, next = null, random = null) {
// this.val = val;
// this.next = next;
// this.random = random;
// }
// }
class Solution {
/**
* @param {Node} head
* @return {Node}
*/
copyRandomList(head) {
const oldToCopy = new Map();
oldToCopy.set(null, null);
let cur = head;
while (cur !== null) {
if (!oldToCopy.has(cur)) {
oldToCopy.set(cur, new Node(0));
}
oldToCopy.get(cur).val = cur.val;
if (!oldToCopy.has(cur.next)) {
oldToCopy.set(cur.next, new Node(0));
}
oldToCopy.get(cur).next = oldToCopy.get(cur.next);
if (!oldToCopy.has(cur.random)) {
oldToCopy.set(cur.random, new Node(0));
}
oldToCopy.get(cur).random = oldToCopy.get(cur.random);
cur = cur.next;
}
return oldToCopy.get(head);
}
}
4. Space Optimized – I
Without using extra space, interweave copied nodes with original nodes in a single list. Assign the next and random pointers in two steps, then separate the original and copied nodes.
- Time complexity: O(n)
- Space complexity: O(1)
Code
C++
Java
Python
JavaScript
C++
/*
// Definition for a Node.
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 == nullptr) {
return nullptr;
}
Node* l1 = head;
while (l1 != nullptr) {
Node* l2 = new Node(l1->val);
l2->next = l1->next;
l1->next = l2;
l1 = l2->next;
}
Node* newHead = head->next;
l1 = head;
while (l1 != nullptr) {
if (l1->random != nullptr) {
l1->next->random = l1->random->next;
}
l1 = l1->next->next;
}
l1 = head;
while (l1 != nullptr) {
Node* l2 = l1->next;
l1->next = l2->next;
if (l2->next != nullptr) {
l2->next = l2->next->next;
}
l1 = l1->next;
}
return newHead;
}
};
Java
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
public class Solution {
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
Node l1 = head;
while (l1 != null) {
Node l2 = new Node(l1.val);
l2.next = l1.next;
l1.next = l2;
l1 = l2.next;
}
Node newHead = head.next;
l1 = head;
while (l1 != null) {
if (l1.random != null) {
l1.next.random = l1.random.next;
}
l1 = l1.next.next;
}
l1 = head;
while (l1 != null) {
Node l2 = l1.next;
l1.next = l2.next;
if (l2.next != null) {
l2.next = l2.next.next;
}
l1 = l1.next;
}
return newHead;
}
}
Python
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
if head is None:
return None
l1 = head
while l1 is not None:
l2 = Node(l1.val)
l2.next = l1.next
l1.next = l2
l1 = l2.next
newHead = head.next
l1 = head
while l1 is not None:
if l1.random is not None:
l1.next.random = l1.random.next
l1 = l1.next.next
l1 = head
while l1 is not None:
l2 = l1.next
l1.next = l2.next
if l2.next is not None:
l2.next = l2.next.next
l1 = l1.next
return newHead
JavaScript
// class Node {
// constructor(val, next = null, random = null) {
// this.val = val;
// this.next = next;
// this.random = random;
// }
// }
class Solution {
/**
* @param {Node} head
* @return {Node}
*/
copyRandomList(head) {
if (!head) {
return null;
}
let l1 = head;
while (l1) {
const l2 = new Node(l1.val);
l2.next = l1.next;
l1.next = l2;
l1 = l2.next;
}
const newHead = head.next;
l1 = head;
while (l1) {
if (l1.random) {
l1.next.random = l1.random.next;
}
l1 = l1.next.next;
}
l1 = head;
while (l1) {
const l2 = l1.next;
l1.next = l2.next;
if (l2.next) {
l2.next = l2.next.next;
}
l1 = l1.next;
}
return newHead;
}
}
5. Space Optimized – II
Modify the interweaving approach to assign next and random pointers in a single traversal while separating the original and copied lists. This approach minimizes passes and maintains O(1) space.
- Time complexity: O(n)
- Space complexity: O(1)
Code
C++
Java
Python
JavaScript
C++
/*
// Definition for a Node.
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* l1 = head;
while (l1) {
Node* l2 = new Node(l1->val);
l2->next = l1->random;
l1->random = l2;
l1 = l1->next;
}
Node* newHead = head->random;
l1 = head;
while (l1) {
Node* l2 = l1->random;
l2->random = (l2->next != nullptr) ? l2->next->random : nullptr;
l1 = l1->next;
}
l1 = head;
while (l1) {
Node* l2 = l1->random;
l1->random = l2->next;
l2->next = (l1->next != nullptr) ? l1->next->random : nullptr;
l1 = l1->next;
}
return newHead;
}
};
Java
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
public class Solution {
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
Node l1 = head;
while (l1 != null) {
Node l2 = new Node(l1.val);
l2.next = l1.random;
l1.random = l2;
l1 = l1.next;
}
Node newHead = head.random;
l1 = head;
while (l1 != null) {
Node l2 = l1.random;
l2.random = (l2.next != null) ? l2.next.random : null;
l1 = l1.next;
}
l1 = head;
while (l1 != null) {
Node l2 = l1.random;
l1.random = l2.next;
l2.next = (l1.next != null) ? l1.next.random : null;
l1 = l1.next;
}
return newHead;
}
}
Python
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
if head is None:
return None
l1 = head
while l1:
l2 = Node(l1.val)
l2.next = l1.random
l1.random = l2
l1 = l1.next
newHead = head.random
l1 = head
while l1:
l2 = l1.random
l2.random = l2.next.random if l2.next else None
l1 = l1.next
l1 = head
while l1 is not None:
l2 = l1.random
l1.random = l2.next
l2.next = l1.next.random if l1.next else None
l1 = l1.next
return newHead
JavaScript
// class Node {
// constructor(val, next = null, random = null) {
// this.val = val;
// this.next = next;
// this.random = random;
// }
// }
class Solution {
/**
* @param {Node} head
* @return {Node}
*/
copyRandomList(head) {
if (head === null) {
return null;
}
let l1 = head;
while (l1) {
let l2 = new Node(l1.val);
l2.next = l1.random;
l1.random = l2;
l1 = l1.next;
}
let newHead = head.random;
l1 = head;
while (l1) {
let l2 = l1.random;
l2.random = l2.next ? l2.next.random : null;
l1 = l1.next;
}
l1 = head;
while (l1) {
let l2 = l1.random;
l1.random = l2.next;
l2.next = l1.next ? l1.next.random : null;
l1 = l1.next;
}
return newHead;
}
}
