Logicmojo - Updated Aug 28, 2021
Problem Statement: Clone List with Random Pointer
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.
Example:
head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
We have presented two approaches to solve the problem:
• Using - Extra Space• Without using - Extra Space
Approach 1: Using extra space
An intuitive solution is to keep a hash table for each node in the list, via which we just need to iterate the list in 2 rounds respectively to create nodes and assign the values for their random pointers. As a result, the space complexity of this solution is O(N), although with a linear time complexity.
C++ Implementation:class Solution { public: Node* copyRandomList(Node* head) { map<Node*, Node*> m; int i=0; Node* ptr = head; while (ptr) { m[ptr] =new Node(ptr->val); ptr = ptr->next; } ptr = head; while (ptr) { m[ptr]->next = m[ptr->next]; m[ptr]->random = m[ptr->random]; ptr = ptr->next; } return m[head]; } };
Python Implementation:
class Node: def __init__(self, val): self.val = val self.next = None self.random = None def copyRandomList(head): if head is None: return None mapping = {} cur = head while cur: mapping[cur] = Node(cur.val) cur = cur.next cur = head while cur: if cur.next: mapping[cur].next = mapping[cur.next] if cur.random: mapping[cur].random = mapping[cur.random] cur = cur.next return mapping[head] def display(head): while head: if head.random: print(head.val, f"({head.random.val})", end=' -> ') else: print(head.val, "(X)", end=' -> ') head = head.next print("X") if __name__=='__main__': head = Node(3) head.next = Node(4) head.next.next = Node(5) head.next.next.next = Node(6) head.next.next.next.next = Node(7) head.random = head.next head.next.random = head head.next.next.random = head.next.next.next.next head.next.next.next.random = head.next.next.next.next head.next.next.next.next.random = head.next display(head) head1 = copyRandomList(head) display(head1)
Time Complexity: O(N)
Space Complexity: O(N)
Approach 2: Without using Extra space
As an optimised solution, we could reduce the space complexity into constant. The idea is to associate the original node with its copy node in a single linked list. In this way, we don't need extra space to keep track of the new nodes.
The algorithm is composed of the follow three steps which are also 3 iteration rounds.
1. Iterate the original list and duplicate each node. The duplicate of each node follows its original immediately.
2. Iterate the new list and assign the random pointer for each duplicated node.
3. Restore the original list and extract the duplicated nodes.
C++ Implementation:
class Solution { public: Node* copyRandomList(Node* head) { Node * head_cp = nullptr, * cur = head, * cur_cp = nullptr; if (head == nullptr) return nullptr; while (cur != nullptr) { cur_cp = new Node(cur->val, cur->next, nullptr); cur->next = cur_cp; cur = cur_cp->next; } cur = head; while (cur != nullptr) { cur_cp = cur->next; if (cur->random) cur_cp->random = cur->random->next; cur = cur_cp ->next; } cur = head; head_cp = head->next; while (cur != nullptr) { cur_cp = cur->next; cur->next = cur_cp->next; cur = cur->next; if (cur) cur_cp->next = cur->next; } return head_cp; } };
Python Implementation:
class Node: def __init__(self, val): self.val = val self.next = None self.random = None def copyRandomList(head): if not head: return head # Creating clone of nodes 1-2-3 = 1-1-2-2-3-3 ptr = head while ptr: copy = Node(ptr.val) copy.next = ptr.next ptr.next = copy ptr = copy.next # assigning random pointer to the copy node ptr = head while ptr: copy = ptr.next copy.random = ptr.random.next if ptr.random else None ptr = copy.next # detaching the copy node and return newhead ptr = head newhead = head.next while ptr: copy = ptr.next ptr.next = copy.next copy.next = copy.next.next if copy.next else None ptr = ptr.next return newhead def display(head): while head: if head.random: print(head.val, f"({head.random.val})", end=' -> ') else: print(head.val, "(X)", end=' -> ') head = head.next print("X") if __name__=='__main__': head = Node(3) head.next = Node(4) head.next.next = Node(5) head.next.next.next = Node(6) head.next.next.next.next = Node(7) head.random = head.next.next.next head.next.random = head head.next.next.random = head.next.next.next.next head.next.next.next.random = head.next.next.next.next head.next.next.next.next.random = head.next display(head) head1 = copyRandomList(head) display(head1)
Time Complexity: O(N)
Space Complexity: O(1)
With this article at Logicmojo, you must have the complete idea of solving Clone a linked list with random pointer problem.