Deep copy linked list C++
Solution:We will discuss two solutions here: one is time optimized and another one is space optimized, as discussed below:#1. Solution with O(n) Time Complexity and O(n) Extra Space Complexity:Just think if the problem were to do a deep copy of a linkedlist with only next pointer and no random pointer. Won't it be so easy ? You just iterate over the given linked list and for each node you create a node and point the next pointer of previous node to it. In the first part of our implementation we do exactly this, but along with that we also do a node to node mapping between the given linked list and the linked list we are creating so that we can come back and take care of the random pointers, which is done in the second part of the implementation. Look at the code below and it will become clear to you.First part of code: Map< Node, Node > nodeToNodeMapping = new HashMap<>(); Node newHead = new Node(head.val); Node curr1 = head; Node curr2 = newHead; nodeToNodeMapping.put(head, newHead); // Build the new linkedlist first, only with next pointer. // We will bother about random pointer later while (curr1.next != null) { Node nextNode1 = curr1.next; Node nextNode2 = new Node(nextNode1.val); curr2.next = nextNode2; nodeToNodeMapping.put(nextNode1, nextNode2); curr1 = curr1.next; curr2 = curr2.next; } Second part of code: Node curr1 = head; Node curr2 = newHead; // let's get the random pointers done now while (curr1 != null) { Node randomNode1 = curr1.random; if (randomNode1 != null) { curr2.random = nodeToNodeMapping.get(randomNode1); } curr1 = curr1.next; curr2 = curr2.next; } Complete Code: This is a Premium content. #2. Solution with O(n2) Time Complexity and O(1) Space Complexity i.e No Extra Space:Ask yourself: why did we have the keep map data structure in the above implementation ? We need the map because we know to which node the random pointer points to in the given linked list, but in the newly created linked list we do not know to which node we should point the random pointer. Also we cannot point to the random node at the same time as that of the new linked list creation, because the random node for a node may not have been created yet. Example, say 3rd node's random pointer points to 10th node. Since we are creating the node in sequential order when we are creating 3rd node at that only 1st and 2nd node are present (along with 3rd node) and 10th node has not been created yet. So we see we have room for improvement on space if we can tolerate to have worse time complexity. What we will do is: after we have created the new linked list with just the next pointers, we iterate over both the linked lists again and for each node in the given linked list we try to find out how far is the node from the head to which its random pointer points to. We use this information to correctly handle the random pointers for the newly created linked list. Take a loot at the code below and you would know what I mean.
This is a Premium content. The above content is written by:
If you have any feedback, please use this form: https://thealgorists.com/Feedback. Subscribe to Our Youtube Channel Follow Us On LinkedIn
You are given a linked list where the node has two pointers. The first is the regular next pointer. The second pointer is called arbitrary_pointer and it can point to any node in the linked list. Your job is to write code to make a deep copy of the given linked list. Here, deep copy means that any operations on the original list (inserting, modifying and removing) should not affect the copied list. Here’s an example of a linked list with arbitrary pointers connected. HintTry it yourselfLinkedListNode* deep_copy_arbitrary_pointer( LinkedListNode* head) { //TODO: Write - Your - Code return NULL; } LinkedListNode* deep_copy_arbitrary_pointer(
LinkedListNode* head) {
if (head == nullptr) {
return nullptr;
}
LinkedListNode* current = head;
LinkedListNode* new_head = nullptr;
LinkedListNode* new_prev = nullptr;
unordered_map
Linear, O(n). Memory ComplexityLinear, O(n). Solution BreakdownThis approach uses a map to track arbitrary nodes pointed by the original list. You will create a deep copy of the original linked list (say list_orig) in two passes.
|