How to create deep copy of Linked List that maintain same order

Question

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.

Answer 1

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.

Answer 2

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;
    }
}