Last Updated: 22 Dec, 2020
Clone a Linked List with random pointers
Easy
Asked in companies
You are given a linked list containing 'n' nodes, where every node in the linked list contains two pointers:
(1) ‘next’ which points to the next node in the list
(2) ‘random’ which points to a random node in the list or 'null'.
Your task is to create a 'deep copy' of the given linked list and return its head.
Note:
A 'deep copy' of a linked list means we do not copy the references of the nodes of the original linked list, rather for each node in the original linked list, a new node is created.
Input Format:
The first line of the input contains an integer 'n', denoting the number of nodes in the 'linked list'.
The second line of the input contains 'n' spaced integers, representing the elements of the linked list, where 'next' pointer of 'ith' node points to 'i+1'th node.
The third line of the input contains 'n' spaced integers, where 'ith' integer 'ri' represents the index (0-indexed) of the node that the random pointer of 'ith' node points to, or '-1' if 'random' pointer points to 'null'.
Output Format:
Return the 'head' node of final linked list.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function. We will validate your returned linked list. "True" will be printed if the linked list was cloned successfully and "False" otherwise.
Approaches
The basic idea is to consider the linked list like a binary tree. Every node of the Linked List has 2 pointers. So we consider these nodes as binary tree nodes. The head of the list becomes the root of the tree. So what we basically have to do now is to traverse the binary tree and clone it. The main issue that we need to tackle here is that of loops.
We start from the root node, and we keep traversing the tree (list), and we keep generating new nodes whenever we find a node for which the clone has not been generated. For example, we were at node A, and we used the next pointer to go to node B, and we created B’, which is a new node B with the same data. Also, say there was a random pointer from A to B. In this case, we don’t have to create yet another copy of node B because B’ already exists. We need to take care of this as well.
Steps are as follows:
- Base case: If the current node is not present in the linked list, return null.
- Check if we have already processed the current node (using HashMap), then simply return the cloned version of it.
- Else, create a new node with the data same as the old node, i.e. copy the node.
- Save this value in the HashMap. This is needed to avoid the loops which might be there while traversing the list.
- Recursively copy the remaining linked list starting once from the next pointer and then from the random pointer.
- Finally, update the next and random pointers for the new node created and return it.
This iterative solution does not model the input as a tree and instead simply treats it as a LinkedList. The idea is to use Hashing to keep track of the links between the old nodes and the new nodes.
Algorithm:
We can solve this problem in two passes.
In the first pass over the original list, we can create an exact clone of the nodes of the original linked list. Additionally, we have a HashMap that maintains the old node to new node mapping. We will need it later on.
Note that the next and random pointers are not yet cloned.
In the second pass, we clone the next and the random pointer. The random pointer for A’ (A’ is the cloned version of the node A) is the HashMap value of the node pointed to by the random pointer of A.
Return the head of the cloned linked list.
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.
Algorithm:
The algorithm is composed of the following three steps which are also 3 iteration rounds.
- Iterate the original list and create a copy of each node. The copy
of each node follows its original immediately, i.e insert each copied node after its corresponding node in the original linked list.
For example, If the original linked list is: 1->2->3
The modified list will be, 1->1->2->2->3->3
- Iterate the new list (original list after modification in step 1) and assign the random pointer for each duplicated/copied node.
- Initialise a pointer to the node, ‘temp’ that points to the second node of the modified linked list.
- Iterate the list again and restore the original list and extract the duplicate nodes, i.e separate the copied from the modified list.
- The duplicated/copied nodes form a linked list which is the clone of the original linked list.
- Return the head of this cloned linked list stored in ‘temp’.
Similar problems