Before moving forward, remember that there are two different methods to copy a node in a linked list. <\/p>\n\n\n\n
One is a shallow copy in this you create a node whose address is the same as the original node. So if you made any changes in this it will also reflect in the original node. Another way is a deep copy in this you create a node and copy the values of the original node.<\/p>\n\n\n\n
In the Copy List with Random Pointer problem, we are given a linked list with an additional random pointer that can point to any node. We need to create a deep copy of this linked list in which none of the nodes have the same address as the original list.\u00a0<\/strong><\/p>\n\n\n\n Let\u2019s look at the example for more clarity:<\/p>\n\n\n\n In this, we are given a linked list of 3 nodes x, y, and z as shown. We have to create 3 more nodes which are exact replicas of x,y, and z the only difference is that they have different addresses.<\/p>\n\n\n\n The brute force approach is to first create n (n is the number of nodes in a linked list.) different nodes having the same values as the original linked list. Store each node address in a linked list as a key in the hash map and the value of those keys is the address of newly created nodes by you. <\/p>\n\n\n\n After mapping iterate a loop and assign next and random values to the newly created nodes.<\/p>\n\n\n\n Let\u2019s examine this approach through an example:<\/p>\n\n\n\n The time complexity for the above code is O(n log(n) ). We are storing each node into the map which took O(n log(n) ) time. We are also iterating over the map whose time complexity is O(n), so the overall time complexity is O(n log(n) ). <\/p>\n\n\n\n The space complexity for the above code is O(n) as we are storing each node on the map. (n is the number of nodes in a linked list.)<\/p>\n\n\n\n In the above approach, we are using an extra space which can be reduced if we do not use the hash map. Also storing values on the map takes extra time. In this approach, we will create a new node next to each node as a copy of the original nodes. <\/p>\n\n\n\n Let\u2019s understand this approach step by step:<\/p>\n\n\n\n Let\u2019s examine the code for the given linked list.<\/p>\n\n\n\n Below is the implementation of the optimized code in C++:<\/p>\n\n\n\n Here is the solution in Java:<\/p>\n\n\n\n We can also implement it in Python to copy the list with a random pointer:<\/p>\n\n\n\n Output:<\/strong> <\/p>\n\n\n\n The time complexity is now reduced to O(n) as we are just iterating over the linked list two times. The Space Complexity is reduced to O(1) as we are not using any extra space.<\/p>\n\n\n\n We can compare the difference the optimized approach makes to copy the list with a random pointer:<\/p>\n\n\n\n![\"Example](\"https:\/\/lh7-us.googleusercontent.com\/9PQKbQM4bCAgliZtTTW0Dt3rOPX8myhdhJFvB6Ndx05vjOu8yVMn18czF-izFP30Vyx4_bSJXo0tSi0OLKYYqc51_zeq3ozx7Q1TgjfBKP5A4lM8Vw6nj_VkQXiaCTSFacakWBQMsZuvn2DUfLA3Wso\")
Hash-Map Approach<\/strong><\/h2>\n\n\n\n
![\"Given](\"https:\/\/lh7-us.googleusercontent.com\/2L-lEKXB9OAyrQNBKyHWxsfs4VmhYjxbTLsIbSglBPbUtYw98Gw_-kZEkAKiZnsGg0AHGegP4_Hi59q0Zq0CNA_z4OSEaXuQZHqgqYVxm34Tjs7tRM1vz4JcYTIxA-K31YWswsQ0-aLxgfVFWNjXLi4\")
\n
![\"Resultant](\"https:\/\/lh7-us.googleusercontent.com\/0kmV9ll2b8Lan-AUSQrHtflk5hGXCU6_iIDaUn9VDtQQmc19PvOHFscdW-ph_3oSr5b95Joi1qIa7eyPc6uoYpOsSr9hKMJhcgy-2QcaTXAI-_4uNbYtDixmhd5Bp9gQyMmGbiAVYIkrScGTTBMRz1Y\")
\n
Optimized Approach<\/strong><\/h2>\n\n\n\n
\n
![\"Example](\"https:\/\/lh7-us.googleusercontent.com\/Z-Wf6RFEG27bz5-l_pu7GYdRIXItYae3XFTdbaY5Q0BrZxtTCAdIwLFEJsAK5AtLmCtLwtp_LkZurt4HvTYPzGe_xlfkw_1VzrqyJoJ7JpzTR63rNbdcjP3jNcfc0yC7B-kIFKAvIahZytbF3GU6Uc0\")
C++ Code<\/strong><\/h3>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\n\nclass node {\n public:\n int val;\n node *next, *random;\n node(int x) {\n val = x;\n next = random = NULL;\n }\n};\n\nnode* new_list(node* head) {\n \n\tif (head == NULL) {\n\t\treturn NULL;\n\t}\n\t\n\tnode* curr = head;\n\twhile (curr != NULL) {\n\t\tnode* temp = new node(curr->val);\n\t\ttemp->next = curr->next;\n\t\tcurr->next = temp;\n\t\tcurr = temp->next;\n\t}\n\t\n\tcurr = head;\n\twhile (curr != NULL) {\n\t\tif (curr->random != NULL) {\n\t\t\tcurr->next->random = curr->random->next;\n\t\t}\n\t\tcurr = curr->next->next;\n\t}\n\t\n\tcurr = head;\n\tnode* clonedhead = head->next;\n\tnode* clonedcurr = head->next;\n\twhile (clonedcurr->next != NULL) {\n\t\tcurr->next = curr->next->next;\n\t\tclonedcurr->next = clonedcurr->next->next;\n\t\tcurr = curr->next;\n\t\tclonedcurr = clonedcurr->next;\n\t}\n\tcurr->next = NULL;\n\tclonedcurr->next = NULL;\n\t\n\treturn clonedhead;\n}\n\nvoid printList(node* head)\n{\n\tcout << head->val << "(";\n\tif(head->random) cout<<head->random->val;\n\telse cout<<"NULL";\n\t\tcout << ")";\n\thead = head->next;\n\twhile (head != NULL) {\n\t\tcout << " -> " << head->val << "(";\n\t\tif(head->random) cout<< head->random->val; \n\t\telse cout<<"NULL";\n\t\tcout<< ")";\n\t\thead = head->next;\n\t}\n\tcout << endl;\n}\n\nint main()\n{\n\t\/\/ Creating a linked list with a random pointer\n\tnode* head = new node(1);\n\thead->next = new node(2);\n\thead->next->next = new node(3);\n\n head->random = head->next->next;\n head->next->random = head;\n\n\t\/\/ the original list\n\tcout << "Original linked list: ";\n\tprintList(head);\n \n\tnode* sol = new_list(head);\n\t\n\tcout << "Cloned linked list: ";\n\tprintList(sol);\n\t\n\treturn 0;\n}<\/pre><\/div>\n\n\n\nJava Code<\/strong><\/h3>\n\n\n\n
import java.util.HashMap;\n\nclass Node {\n public int val;\n public Node next, random;\n\n public Node(int x) {\n val = x;\n next = random = null;\n }\n}\n\npublic class CopyListWithRandomPointer {\n\n public Node copyRandomList(Node head) {\n if (head == null) return null;\n\n Node curr = head;\n\n \/\/ Create a new node for each existing node and insert it after the original node\n while (curr != null) {\n Node temp = new Node(curr.val);\n temp.next = curr.next;\n curr.next = temp;\n curr = temp.next;\n }\n\n curr = head;\n\n \/\/ Assign random pointers for the new nodes\n while (curr != null) {\n if (curr.random != null)\n curr.next.random = curr.random.next;\n curr = curr.next.next;\n }\n\n \/\/ Separate the original and cloned nodes\n curr = head;\n Node clonedHead = head.next;\n Node clonedCurr = head.next;\n\n while (clonedCurr.next != null) {\n curr.next = curr.next.next;\n clonedCurr.next = clonedCurr.next.next;\n curr = curr.next;\n clonedCurr = clonedCurr.next;\n }\n\n curr.next = null;\n clonedCurr.next = null;\n\n return clonedHead;\n }\n\n public static void printList(Node head) {\n Node current = head;\n while (current != null) {\n System.out.print(current.val + "(" + (current.random != null ? current.random.val : "NULL") + ")" + " -> ");\n current = current.next;\n }\n System.out.println("NULL");\n }\n\n public static void main(String[] args) {\n CopyListWithRandomPointer solution = new CopyListWithRandomPointer();\n\n Node head = new Node(1);\n head.next = new Node(2);\n head.next.next = new Node(3);\n\n head.random = head.next.next;\n head.next.random = head;\n\n System.out.print("Original linked list: ");\n printList(head);\n\n Node sol = solution.copyRandomList(head);\n\n System.out.print("Cloned linked list: ");\n printList(sol);\n }\n}<\/pre><\/div>\n\n\n\nPython Code<\/strong><\/h3>\n\n\n\n
class Node:\n def __init__(self, x):\n self.val = x\n self.next = None\n self.random = None\n\ndef copyRandomList(head: 'Node') -> 'Node':\n if head is None:\n return None\n\n curr = head\n\n # Create a new node for each existing node and insert it after the original node\n while curr:\n temp = Node(curr.val)\n temp.next = curr.next\n curr.next = temp\n curr = temp.next\n\n curr = head\n\n # Assign random pointers for the new nodes\n while curr:\n if curr.random:\n curr.next.random = curr.random.next\n curr = curr.next.next\n\n # Separate the original and cloned nodes\n curr = head\n cloned_head = head.next\n cloned_curr = head.next\n\n while cloned_curr.next:\n curr.next = curr.next.next\n cloned_curr.next = cloned_curr.next.next\n curr = curr.next\n cloned_curr = cloned_curr.next\n\n curr.next = None\n cloned_curr.next = None\n\n return cloned_head\n\ndef print_list(head: 'Node'):\n current = head\n while current:\n print(f"{current.val}({current.random.val if current.random else 'NULL'}) ->", end=" ")\n current = current.next\n print("NULL")\n\nif __name__ == "__main__":\n # Creating a linked list with random pointer\n head = Node(1)\n head.next = Node(2)\n head.next.next = Node(3)\n\n head.random = head.next.next\n head.next.random = head\n\n # the original list\n print("Original linked list: ", end="")\n print_list(head)\n\n sol = copyRandomList(head)\n\n print("Cloned linked list: ", end="")\n print_list(sol)<\/pre><\/div>\n\n\n\n Original linked list: 1(3) -> 2(1) -> 3(NULL)\n Cloned linked list: 1(3) -> 2(1) -> 3(NULL)<\/code><\/pre>\n\n\n\n