How to create a deep copy of a Linked List that maintains the same order
During the interview I was asked the following question which I could not understand. You are presented with a linked list of the following Node elements:
class Node {
int value;
Node next; // points to next element in list
Node random; // points to one random element of list
}
Let's say you have a Linked List of these nodes (for example, 20 nodes), where "next" points to the next item and “random" points to one other item in the list (which means it may point to one specific but randomly selected item in list). Ie, 1st element "random" can point to Node # 5, Node 2nd element random can point to Node # 9, etc.
Question . How do you create a new Linked List that is a deep copy of this list of nodes, but maintains the same ordering and the same links for "random" and "follow-up"?
In other words, if one of them traverses this new list using either of these two pointers, the traversal order will be the same.
Another topic that some people have been referring to would be cloning the same pointers via the default clone and this will not solve this problem.
source to share
Terminate all nodes and put all nodes in HashMap
with key Node as and new Node instance as value.
Map<Node, Node> nodeMap = new HashMap<>();
...
nodeMap.put(currentNode, new Node();
Now you are iterating over all your "old" nodes again, just by going through node.next
, and for each Node, you will copy the nodes so that you refer to the map value instead of the old Node.
Node newNode = nodeMap.get(currentNode);
newNode.value = currentNode.value;
newNode.next = nodeMap.get(currentNode.next);
newNode.random = nodeMap.get(currentNode.random);
After that, you should have an exact copy without duplicate copies.
source to share
After searching the internet for a while, I found this problem with an answer. Pretty hard. They present this basic solution:
- copy each node, i.e. duplicate each node and paste it into the list
- copy random pointers for all newly created nodes
- split the list in two
See it here: http://www.programcreek.com/2012/12/leetcode-copy-list-with-random-pointer/
source to share
import java.util.*;
public class Solution {
HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null)
return null;
if (map.containsKey(head))
return map.get(head);
RandomListNode node = new RandomListNode(head.label);
map.put(head, node);
node.next = copyRandomList(head.next);
node.random = copyRandomList(head.random);
return node;
}
}
source to share