This problem can be solved by 2 ways:
- Using HashMap
- Using O(n) time and Constant Space O(1)
We shall discuss both of the solutions here.
-
Using HashMap
We take 2 loops. In the first loop we copy the data into our new list.
In the second loop, we create the links for the “next” and “random” pointers from the first list.
-
Using O(n) time and Constant Space O(1)
In this solution, we take 3 loops.
In the first loop, we create a new copy of the list and place it next to the original list.
Example:
1 -> 2 -> 3 -> 4 -> 5
After the first loop,
1 -> 1 -> 2 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5 -> 5
In the second loop, we copy the random link
In the third loop, since we have both the original and copy in the same list, we divide them both.
Solution in C++
#include<iostream> #include<vector> #include<string> #include<unordered_map> using namespace std; struct Node { public: int data; Node *next; Node *random; Node(int x) { data = x; next = random = NULL; } }; Node *solution_using_unordered_map(Node *head) { unordered_map<Node*, Node*> umap; Node *curr = head; // copy the data into the new list while(curr) { umap[curr] = new Node(curr->data); curr = curr->next; } curr = head; while(curr) { //copy where the next should point umap[curr]->next = umap[curr->next]; // copy where the random should point umap[curr]->random = umap[curr->random]; curr = curr->next; } // return the head of the new list return umap[head]; } Node* solution_using_O_1(Node* head) { if (!head) { return NULL; } // create copy into the existing linked list so that every other odd node is the original list //and every other even node is the copy of the original list Node *orig=head; Node *copy=NULL; while (orig) { // // create and insert copy after each orig node // copy = new Node(orig->data); copy->next = orig->next; orig->next = copy; // // skip over newly inserted copied node (orig->next), // and iterate to original's next (orig->next->next) // orig = orig->next->next; } // // now update the random pointers, // the copy's random will be the original random's "next" node, // since every other node is a copy of the original node // orig = head; while (orig) { // every other node is a copy of the original copy = orig->next; // // set copy's random to original random's next, // since copy is original offset by 1 next // if (orig->random){ copy->random = orig->random->next; } // // skip over copied node (itr->next), // and move onto original's next (orig->next->next) // orig = orig->next->next; } // // take all originals (odd nodes) and link them back together, // take all copies (even nodes) and link them together, // then return the head of this copied list // orig = head; Node* copyHead = head->next; // head is odd, head->next is even copy = copyHead; while (copy && copy->next){ orig->next = orig->next->next; // odd copy->next = copy->next->next; // even // // iterate forward // orig = orig->next; copy = copy->next; } // // one last update needed to remove the last copied node // from the original list // orig->next = NULL; return copyHead; } void print_list(Node *head) { Node *ptr = head; while(ptr) { cout<<"Data = "<< ptr->data << " Random Data = "<< ptr->random->data<<endl; ptr = ptr->next; } } int main() { Node *start = new Node(1); start -> next = new Node(2); start -> next -> next = new Node(3); start -> next -> next -> next = new Node(4); start -> next -> next -> next -> next = new Node(5); //1st random points to 3rd start -> random = start -> next -> next; // 2nd random points to 1st start -> next -> random = start; // 3rd random points to 5 th start-> next -> next -> random = start -> next -> next -> next -> next; // 4th random points to 5 th start -> next -> next -> next -> random = start -> next -> next -> next -> next; // 5th random points to 2nd start -> next -> next -> next -> next -> random = start -> next; cout << "Given list : \n"; print_list(start); Node *result_using_unordered_map = solution_using_unordered_map(start); cout << "\n\nResult of the list using unordered_map: \n"; print_list(result_using_unordered_map); Node *result_using_O_1 = solution_using_O_1(start); cout << "\n\nResult of the list using O (1): \n"; print_list(result_using_O_1); return 0; }
Output:
Given list : Data = 1 Random Data = 3 Data = 2 Random Data = 1 Data = 3 Random Data = 5 Data = 4 Random Data = 5 Data = 5 Random Data = 2 Result of the list using unordered_map: Data = 1 Random Data = 3 Data = 2 Random Data = 1 Data = 3 Random Data = 5 Data = 4 Random Data = 5 Data = 5 Random Data = 2 Result of the list using O (1): Data = 1 Random Data = 3 Data = 2 Random Data = 1 Data = 3 Random Data = 5 Data = 4 Random Data = 5 Data = 5 Random Data = 2
Maneesh Reddy
public static Node deepCopy(Node head){
Node prevNode = null;
Node currNode = null;
Node newHead = null;
while(head != null){
currNode = new Node(head.data);
if(prevNode != null){
prevNode.next = currNode;
}
else{
newHead = currNode;
}
prevNode = currNode;
head = head.next;
}
return newHead;
}