Duplicate a LinkedList with a pointer to a random node apart from the next node

Question

Q: Every node of the linked list has a random pointer (in addition to the next pointer) which could randomly point to another node or be null. How would you duplicate such a linkedlist?

A: Here's what I have, I just wanted to ratify if this was the optimal way of doing it.

Since there's no space constraints specified, I'm going to use a LinkedHashSet and a LinkedHashMap (I can imagine people nodding their head in disagreement already ;) )

First Iteration: Do the obvious - read each node from the list to be copied and create nodes on the new list. Then, read the random node like so: this.random.data and insert into the LinkedHashSet.

Second Iteration: Iterate through the new list and add each node's data as the first column and the node itself as the second column into the LinkedHashMap (doesn't have to be Linked, but I'm just going with the flow).

Third Iteration: Iterate over the LinkedHashSet (this is the reason why this needs to be Linked - predictable ordering) and the new list simultaneously. For the first node, read the first entry of the LinkedHashSet, look up the corresponding object in the LinkedHashMap and add as the random node to the current node in the new list.

3 iterations does seem a little crazy, but the attempt was to keep the complexity as O(N). Any solution that improves on the O(3N) space requirement and O(3N) runtime complexity would be great. Thanks!

---

Edit: The entry from the LinkedHashSet can be removed when making an entry into the LinkedHashMap, so this would only take O(2N) space.

Answer 1

As pointed out by MahlerFive, I think you can do this with O(2N) runtime complexity, and O(N) space complexity.

Let's assume you have

public class Node {
    private Node next;
    private Node random;
    private String data;
    // getters and setters omitted for the sake of brevity
}

I would do a deep copy of a linked list of Nodes as:

private Node deepCopy(Node original) {
    // We use the following map to associate newly created instances 
    // of Node with the instances of Node in the original list
    Map<Node, Node> map = new HashMap<Node, Node>();
    // We scan the original list and for each Node x we create a new 
    // Node y whose data is a copy of x's data, then we store the 
    // couple (x,y) in map using x as a key. Note that during this 
    // scan we set y.next and y.random to null: we'll fix them in 
    // the next scan
    Node x = original;
    while (x != null) {
        Node y = new Node();
        y.setData(new String(x.getData()));
        y.setNext(null);
        y.setRandom(null);
        map.put(x, y);
        x = x.getNext();
    }
    // Now for each Node x in the original list we have a copy y 
    // stored in our map. We scan again the original list and 
    // we set the pointers buildings the new list
    x = original;
    while (x != null) {
            // we get the node y corresponding to x from the map
        Node y = map.get(x);
            // let x' = x.next; y' = map.get(x') is the new node 
            // corresponding to x'; so we can set y.next = y'
        y.setNext(map.get(x.getNext()));
            // let x'' = x.random; y'' = map.get(x'') is the new 
            // node corresponding to x''; so we can set y.random = y''
        y.setRandom(map.get(x.getRandom()));
        x = x.getNext();
    }
    // finally we return the head of the new list, that is the Node y
    // in the map corresponding to the Node original
    return map.get(original);
}

---

Edit: I found that this question is a duplicate of the one asked here: there you find an answer that shows how to solve this problem in O(3N) runtime complexity with no extra space: very ingenious! But it uses a trick with C pointers, and I'm not sure how to do the same in java.

Answer 2

You can do this with 2N steps and a map with N elements.

1. Walk the old list following the 'next' pointers. For each node you visit, add a node to your new list, connect the previous node in your new list to the new node, store the old node random pointer in the new new node, then store a mapping of the old node pointer to the new node pointer in a map.

2. Walk the new list, and for each random pointer, look it up in the map to find the associated node in the new list to replace it with.