I got asked the following question at a job interview that I could not figure out. You are given 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
}
Say you have a Linked List of these nodes (say 20 nodes) where "next" points to the next element and "random" points to one other element of the list (meaning, can point to one specific but randomly chosen element in the list). I.e., 1st element's "random" can point to node #5, Node 2nd element's random can point to node #9, etc.
Question: How do you create a brand new Linked List that is a deep copy of this list of Nodes but maintains the same order and same linkages for both "random" and "next"?
In other words, if one traverses this new list using any of these 2 pointers the order of traversal would be the same.
The other topic some people referenced would clone the same pointers via default clone and that would not address this challenge.
Loop all Nodes and put all nodes into a HashMap
with the Node as key and a new Node instance as value.
Map<Node, Node> nodeMap = new HashMap<>();
...
nodeMap.put(currentNode, new Node();
Now you again iterate over all your "old" nodes by just looping through node.next
and for each node you copy the nodes such that you are referencing the value of the map instead the old node itself.
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 duplicated instances.