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.

Possible duplicate of [How to clone ArrayList and also clone its contents?](https://stackoverflow.com/questions/715650/how-to-clone-arraylist-and-also-clone-its-contents) — Tavo, Jul 14 '17 at 01:16

score 3 · Answer 1 · answered Jul 14 '17 at 01:36

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.

score 1 · Answer 2 · answered Feb 02 '19 at 08:21

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

score 0 · Answer 3 · answered Jul 14 '17 at 01:34

0

After searching online for a while I found this problem with an answer. Pretty tricky. They present this main solution:

copy every node, i.e., duplicate every node, and insert it to the list
copy random pointers for all newly created nodes
break the list to two

See here: http://www.programcreek.com/2012/12/leetcode-copy-list-with-random-pointer/

answered Jul 14 '17 at 01:34

user1385969

195
2
2
11

Do we need to insert the duplicated nodes in the same list really? Can't we create a new head and copy the next pointer from original list. Then iterate over it once more to copy the random pointer. Will this work? – CodeHunter Jul 14 '17 at 07:08

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

3 Answers3