Naive O(n^2) time O(n) space solution (accepted)
This is a very naive approach and can be skipped as other approaches do not rely on this. The idea is to create new corresponding nodes and store them in a vector. Then loop through the vector and assign the next pointer as the next element in vector. Then, to assign the random pointer, find distance of the node pointed by random pointer in original list from that node.
int getDistance (Node* head, Node* target) {
int dist = 0;
if (head == target)
return 0;
while (head != NULL) {
head = head->next;
dist++;
if (head == target)
return dist;
}
return -1;
}
Node* copyRandomList(Node* head) {
Node* temp = head;
vector<Node*> v;
while (head != NULL) {
v.push_back(new Node(head->val, NULL, NULL));
head = head->next;
}
for (int i=0; i<v.size(); i++) {
if (i==v.size()-1)
v[i]->next = NULL;
else
v[i]->next = v[i+1];
}
head = temp;
int i=0;
while (temp != NULL) {
if (temp->random != NULL) {
int dist = getDistance(head, temp->random);
if (dist != -1)
v[i]->random = v[dist];
} else {
v[i]->random = NULL;
}
temp = temp->next;
i++;
}
if (v.size() > 0)
return v[0];
else
return NULL;
}
O(n) time and O(n) space solution
A good solution to present in an interview would be to store new nodes corresponding to each original node in a map. Then go through the list again and assign respective random pointers using the map. It is pretty straightforward to understand:
Node* copyRandomList(Node* head) {
if (!head)
return NULL;
unordered_map<Node*, Node*> map;
Node* temp = head;
while (temp != NULL) {
map[temp] = new Node(temp->val);
temp = temp->next;
}
temp = head;
while (temp != NULL) {
map[temp]->next = temp->next ? map[temp->next] : NULL;
map[temp]->random = temp->random ? map[temp->random] : NULL;
temp = temp->next;
}
return map[head];
}
O(n) time and O(1) space solution
/*
Consider l1 as a node on the 1st list and l2 as the corresponding node on 2nd list.
Original list: 1->2->3->4
Step 1:
Build the 2nd list by creating a new node for each node in 1st list.
While doing so, insert each new node after it's corresponding node in the 1st list.
Now, list becomes: 1->1'->2->2'->3->3'->4->4'
Step 2:
The new head is the 2nd node as that was the first inserted node (2').
Step 3:
Fix the random pointers in the 2nd list: (Remember that l1->next is actually l2)
l2->random will be the node in 2nd list that corresponds l1->random, which is next node of l1->random.
Step 4:
Separate the combined list into 2: Splice out nodes that are part of second list.
Return the new head that we saved in step 2.
*/
Node *copyRandomList(Node *head) {
Node *newHead, *l1, *l2;
if (head == NULL) return NULL;
for (l1 = head; l1 != NULL; l1 = l1->next->next) {
l2 = new Node(l1->val);
l2->next = l1->next;
l1->next = l2;
}
newHead = head->next;
for (l1 = head; l1 != NULL; l1 = l1->next->next) {
if (l1->random != NULL) l1->next->random = l1->random->next;
}
for (l1 = head; l1 != NULL; l1 = l1->next) {
l2 = l1->next;
l1->next = l2->next;
if (l2->next != NULL) l2->next = l2->next->next;
}
return newHead;
}
Credits: @satyakam
Pictorial representation by @hot13399: See here
