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

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 sp开发者_StackOverflowace 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.

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.

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.

I too was asked this question in interview recently. Here is what i proposed. Create a map of original list nodes where addreess of each node will be key and the offset of random pointer will be the value. Now create a new linked list with random pointer =null from the original map. In the end, iterate through the original list , with the help of map get offset of original pointer and use that offset to link random pointer in newly created map.

Interviewer was not happy in the end.May be looking for some better approach or he had the set answer in his mind and unable to grasp new way of solving it.

in O(n) time and with constant space

public class CloneLinkedListWithRandomPointer {

public static void main(String[] args) throws Exception {
    SpecialLink link = new SpecialLink(1);
    SpecialLink two = new SpecialLink(2);
    SpecialLink three = new SpecialLink(3);
    SpecialLink four = new SpecialLink(4);
    SpecialLink five = new SpecialLink(5);

    link.next = two;
    two.next = three;
    three.next = four;
    four.next = five;

    link.random = four;
    two.random = five;
    three.random = null;
    four.random = five;
    five.random=link;

    SpecialLink copy = cloneSpecialLinkedList(link);

    System.out.println(link);
    System.out.println(copy);
}


public static SpecialLink cloneSpecialLinkedList(SpecialLink link) throws Exception{

    SpecialLink temp = link;
    while(temp != null){
        temp.next = (SpecialLink) temp.clone();
        temp = temp.next==null?temp.next:temp.next.next;
    }

    temp = link;
    while(temp != null){
        temp.next.random = temp.random!=null?temp.random.next:null;
        temp = temp.next==null?temp.next:temp.next.next;
    }


    SpecialLink copy = link.next;

    temp = link;
    SpecialLink copyTemp = copy;

    while(temp.next!= null && copyTemp.next != null){
        temp.next = temp.next.next;
        copyTemp.next = copyTemp.next.next;

        temp = temp.next;
        copyTemp = copyTemp.next;

    }

    return copy;
}

}

class SpecialLink implements Cloneable{

enum Type{
    ORIGINAL,COPY
}

int val;
SpecialLink next;
SpecialLink random;
Type type;

public void setValue(int value){
    this.val = value;
}

public SpecialLink addNode(int value){
    return next = new SpecialLink(value);
}

public SpecialLink(int value) {
    super();
    this.val = value;
    this.type = Type.ORIGINAL;
}

@Override
public String toString() {
    SpecialLink temp = this;
    StringBuilder builder = new StringBuilder();
    while(temp != null){
        builder.append(temp.val).append("--").append(temp.type.toString()).append("->").append(temp.random == null? null:temp.random.val).append("--").append(temp.random == null? null:temp.random.type);
        builder.append(", ");
        temp = temp.next;
    }
    return builder.toString();
}

@Override
public Object clone() throws CloneNotSupportedException {
    // TODO Auto-generated method stub
    SpecialLink clone = (SpecialLink) super.clone();
    clone.type = Type.COPY;
    return clone;
}
}

Walk the list and use clone()?

I wrote code for @MahlerFive 's solution, which works without mapping.

Here's the code:

private static class Node {
    private String item;
    private Node next;
    private Node random;
}

public static Node cloneLinkedStructure(Node head) {
    // make holes after each original node
    for (Node p = head; p != null;) {
        Node pnext = p.next;
        Node hole = new Node();
        hole.item = ".";
        p.next = hole;
        hole.next = pnext;
        p = pnext;
    }

    Node fakeHead = new Node(); // fake new head
    Node q = fakeHead;
    Node p = head;
    while (p != null) {
        // build the new linked structure
        Node oldq = q;
        q = new Node();
        q.item = p.item;
        oldq.next = q;
        q.random = p.random.next; // link to a hole

        Node hole = p.next;
        hole.random = q; // use link RANDOM as a backward link to new node

        p = hole.next;
    }
    q.next = null;

    Node newHead = fakeHead.next; // throw fake head
    // build random links for the new linked structure
    for (q = newHead; q != null; q = q.next)
        q.random = q.random.random;

    // delete holes to restore original linked structure
    for (p = head; p != null; p = p.next)
        p.next = p.next.next;

    return newHead;
}

1) Create the copy of node 1 and insert it between node 1 & node 2 in original Linked List, create the copy of 2 and insert it between 2 & 3.. Continue in this fashion, add the copy of N afte the Nth node

2) Now copy the arbitrary link in this fashion

original->next->arbitrary = original->arbitrary->next;  /*TRAVERSE TWO NODES*/

This works because original->next is nothing but copy of original and Original->arbitrary-> next is nothing but copy of arbitrary. 3) Now restore the original and copy linked lists in this fashion in a single loop.

original->next = original->next->next;
copy->next = copy->next->next;

4) Make sure that last element of original->next is NULL.

Time Complexity: O(n)

Auxiliary Space: O(1)

source

Here is the Java implementation:

public static <T> RandomLinearNode<T> clone(RandomLinearNode<T> head) {
    if (head == null) {
        return head;
    }
    RandomLinearNode<T> itr = head, temp;

    // insert copy nodes after each original nodes
    while (itr != null) {
        temp = new RandomLinearNode<T>(itr.getElement());
        temp.next(itr.next());
        itr.next(temp);
        itr = temp.next();
    }
    // copy the random pointer
    itr = head;
    while (itr != null && itr.next() != null) {
        if (itr.random() != null) {
            itr.next().random(itr.random().next());
        }
        itr = itr.next().next();
    }
    // break the list into two
    RandomLinearNode<T> newHead = head.next();
    itr = head;
    while (itr != null && itr.next() != null) {
        temp = itr.next();
        itr.next(temp.next());          
        itr = temp.next();
    }
    return newHead;
}

Here is the unit tests

@Test
public void cloneLinkeListWithRandomPointerTest() {
    RandomLinearNode<Integer> one = new RandomLinearNode<Integer>(1, null, null);
    RandomLinearNode<Integer> two = new RandomLinearNode<Integer>(2, one, null);
    RandomLinearNode<Integer> three = new RandomLinearNode<Integer>(3, two, null);
    RandomLinearNode<Integer> four = new RandomLinearNode<Integer>(4, three, null);
    RandomLinearNode<Integer> five = new RandomLinearNode<Integer>(5, four, four);
    RandomLinearNode<Integer> six = new RandomLinearNode<Integer>(6, five, two);
    RandomLinearNode<Integer> seven = new RandomLinearNode<Integer>(7, six, three);
    RandomLinearNode<Integer> eight = new RandomLinearNode<Integer>(8, seven, one);

    RandomLinearNode<Integer> newHead = LinkedListUtil.clone(eight);
    assertThat(eight, not(sameInstance(newHead)));
    assertThat(newHead.getElement(), equalTo(eight.getElement()));
    assertThat(newHead.random().getElement(), equalTo(eight.random().getElement()));

    assertThat(newHead.next().getElement(), equalTo(eight.next().getElement()));
    assertThat(newHead.next().random().getElement(), equalTo(eight.next().random().getElement()));

    assertThat(newHead.next().next().getElement(), equalTo(eight.next().next().getElement()));
    assertThat(newHead.next().next().random().getElement(), equalTo(eight.next().next().random().getElement()));


    assertThat(newHead.next().next().next().getElement(), equalTo(eight.next().next().next().getElement()));
    assertThat(newHead.next().next().next().random().getElement(), equalTo(eight.next().next().next().random().getElement()));
}