Given the head of a linked list where each node contains an integer data, a next pointer, and a random pointer, create a deep copy of the entire linked list and return the head of the copied list.
The next pointer connects a node to the next node in the list, while the random pointer can point to any node in the list, including the current node, or null.
The copied list must contain a newly created node for every node in the original list. Each copied node should have the same data value as its corresponding original node, and its next and random pointers should preserve the same relationships.
Most importantly, the copied list must be completely independent of the original list. No next or random pointer in the copied list should point to any node from the original 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]]
Explanation: Each pair stores [node value, random index]. The cloned list keeps the same values and random references by index.
Example 2
Input: head = [[1, 1], [2, 1]]
Output: [[1, 1], [2, 1]]
Explanation: Both cloned nodes point random links to the cloned node at index 1.
Brute Force Approach
Create a separate clone for every original node and maintain a hash map from each original node to its clone. This mapping makes it possible to correctly connect both next and random pointers, since a random pointer can refer to any node in the list.
Algorithm
Return
nullwhenheadis empty, as there are no nodes to clone.Initialize a hash map to store the relationship between every original node and its corresponding cloned node.
Traverse the original list and create one clone for each node, storing the original-to-clone mapping in the hash map.
Traverse the original list again, because all cloned nodes now exist and their target nodes can be found through the mapping.
Set each clone's
nextandrandompointers using the mapped clones of the corresponding original pointers.Return the clone mapped to the original
head, as it represents the starting node of the completely cloned list.
Dry Run
Diagram 1
Solution
#include <bits/stdc++.h>using namespace std;class Node {public: int data; Node* next; Node* random; // Constructor initializes the node value and both pointers. Node(int value) { data = value; next = nullptr; random = nullptr; }};class Solution {public: // Function to clone a linked list containing next and random pointers. Node* copyRandomList(Node* head) { // An empty list has no nodes to clone. if (head == nullptr) { return nullptr; } unordered_map<Node*, Node*> nodeMap; Node* current = head; // Create one cloned node for every original node. // The map keeps the original-to-clone relationship so that // both next and random pointers can later be connected correctly. while (current != nullptr) { nodeMap[current] = new Node(current->data); current = current->next; } current = head; // Connect the pointers of each cloned node using the // original-to-clone mapping created above. while (current != nullptr) { nodeMap[current]->next = nodeMap[current->next]; nodeMap[current]->random = nodeMap[current->random]; current = current->next; } // The clone corresponding to the original head becomes // the head of the completely copied linked list. return nodeMap[head]; }};// Function creates a linked list and assigns the required random links.Node* createList(vector<int>& values, vector<int>& randomIndex) { if (values.empty()) { return nullptr; } vector<Node*> nodes; // Create all nodes first so every node is available when // the next and random pointers are assigned. for (int value : values) { nodes.push_back(new Node(value)); } // Connect consecutive nodes to form the normal linked-list chain. for (int index = 0; index + 1 < (int)nodes.size(); index++) { nodes[index]->next = nodes[index + 1]; } // Assign random pointers using the given target indices. // A value of -1 means the random pointer remains null. for (int index = 0; index < (int)nodes.size(); index++) { if (randomIndex[index] != -1) { nodes[index]->random = nodes[randomIndex[index]]; } } return nodes[0];};// Function prints each node's value along with the index// of the node pointed to by its random pointer.void printList(Node* head) { unordered_map<Node*, int> indexMap; Node* current = head; int index = 0; // Assign an index to every node so random pointers // can be displayed using their corresponding positions. while (current != nullptr) { indexMap[current] = index++; current = current->next; } current = head; // Print each node as [data, randomIndex]. while (current != nullptr) { int randomIdx = current->random ? indexMap[current->random] : -1; cout << "[" << current->data << "," << randomIdx << "]"; if (current->next != nullptr) { cout << " "; } current = current->next; }}// Driver code.int main() { vector<int> values = {7, 13, 11, 10, 1}; vector<int> randomIndex = {-1, 0, 4, 2, 0};Complexity Analysis
Time Complexity: O(N), where N is the total number of nodes. The list is traversed twice, and each node is processed a constant number of times.
Space Complexity: O(N), where N is the total number of nodes. The hash map stores one original-to-clone mapping for every node.
Optimal Approach
Instead of maintaining a hash map, place every cloned node immediately after its corresponding original node. This makes the clone of any original node directly accessible through original->next, allowing random pointers to be connected without extra mapping space.
After all pointers are established, the interleaved structure is separated into the original list and the cloned list.
Algorithm
Return
nullwhenheadis empty, as there are no nodes to clone.Traverse the original list and insert a cloned node immediately after each original node, so every original node is directly followed by its clone.
Traverse the interleaved list again and assign each clone's
randompointer using the node placed after the originalrandomtarget.Keep the clone's
randompointernullwhen the corresponding originalrandompointer isnull, because there is no target to connect.Traverse the interleaved list and restore each original node's
nextpointer while connecting each clone to the next clone, separating both lists.Return the head of the cloned linked list, which is the node immediately after the original
head.
Dry Run
Diagram 1
Solution
#include <bits/stdc++.h>using namespace std;class Node {public: int data; Node* next; Node* random; // Constructor initializes the node value and both pointers. Node(int value) { data = value; next = nullptr; random = nullptr; }};class Solution {public: // Function to clone a linked list using interleaved nodes. Node* copyRandomList(Node* head) { // An empty list has no nodes to clone. if (head == nullptr) { return nullptr; } Node* current = head; // Insert each cloned node immediately after its original node. // This places every original node next to its clone, making the // corresponding target of each random pointer easy to locate. while (current != nullptr) { Node* clonedNode = new Node(current->data); clonedNode->next = current->next; current->next = clonedNode; // Move to the next original node, skipping the clone. current = clonedNode->next; } current = head; // Set the random pointer of every cloned node. // If original->random points to X, then original->random->next // points to X's clone because the nodes are interleaved. while (current != nullptr) { if (current->random != nullptr) { current->next->random = current->random->next; } // Move to the next original node. current = current->next->next; } current = head; Node* clonedHead = head->next; // Separate the interleaved structure back into the original // and cloned linked lists while restoring the original links. while (current != nullptr) { Node* clonedNode = current->next; // Restore the original node's next pointer. current->next = clonedNode->next; // Connect the clone to the next clone, if one exists. if (clonedNode->next != nullptr) { clonedNode->next = clonedNode->next->next; } // Move to the next original node. current = current->next; } // The first cloned node is the head of the copied list. return clonedHead; }};// Function creates a linked list and assigns its random pointers.Node* createList(vector<int>& values, vector<int>& randomIndex) { if (values.empty()) { return nullptr; } vector<Node*> nodes; // Create all nodes first so every random-pointer target // is available before the links are assigned. for (int value : values) { nodes.push_back(new Node(value)); } // Connect consecutive nodes to form the normal linked-list chain. for (int index = 0; index + 1 < (int)nodes.size(); index++) { nodes[index]->next = nodes[index + 1]; } // Assign each random pointer using the given target index. // A value of -1 means the random pointer remains null. for (int index = 0; index < (int)nodes.size(); index++) { if (randomIndex[index] != -1) { nodes[index]->random = nodes[randomIndex[index]]; } } return nodes[0];};// Function prints each node's data along with its random-pointer index.void printList(Node* head) { unordered_map<Node*, int> indexMap; Node* current = head; int index = 0; // Store the position of every node so each random pointer // can be displayed using its corresponding index. while (current != nullptr) { indexMap[current] = index++;Complexity Analysis
Time Complexity: O(N), where N is the number of nodes. Three linear traversals process each node a constant number of times.
Space Complexity: O(1), where N is the number of nodes. No auxiliary data structure grows with the input size; the newly created clone nodes are part of the required output.
Interview follow-up Questions
Yes. A random pointer may point to any node in the list or to null.
Be the first to add a comment.