Clone linked list with random pointers

Clone linked list where a node also has a random pointer apart from next pointer.

e.g.



The problem of cloning a linked list with only next pointer is fairly simple problem. But the trickier part here is to clone random pointer since while cloning the next pointers we don't have a way to determine the node that will be clone of the node random pointer points to.

So the basic ides to solve this problem is to clone the next pointers in the first pass while maintaining a mapping of actual node and cloned node.
In second pass, clone all the next pointers.

The mapping of actual node and cloned node can be achieved by following two ways depending upon problem constraints.
a. If use of extra memory other than memory for cloned nodes is allowed then simplest way is to use hash map to maintain mapping of actual nodes and cloned node. In first pass clone next pointers and keep storing each cloned node in the hash map. In second pass, clone the random pointers.

b. If use of extra memory is not allowed, then we can follow approach of adding cloned node between actual nodes. For example insert 5` (clone of node 5) between node 5 and node 4.

• In first pass keep inserting cloned node between actual node. For above example linked list after first pass will look like:

          5--5'--4--4'--3--3'--2--2'--1--1'

• In second pass clone the random pointers and jumping 2 steps in each iteration.

          For example random pointer of 5' should be next of random pointer of 5. Jump 2 steps to node 4 at the end of iteration

• In third pass, restore all the pointers to split cloned and actual nodes.

Working code:

 import java.util.HashMap;  
 import java.util.Map;  
 /**  
  * Clone a linked list where each node has a next pointer and a random pointer  
  * to any node in the list.  
  *   
  * @author sanahuja  
  *   
  */  
 public class CloneList {  
      static Map<Node, Node> cloneNodes = new HashMap<Node, Node>();  
      public static void main(String[] args) {  
           Node head = new Node(5);  
           Node p1 = new Node(4);  
           Node p2 = new Node(3);  
           Node p3 = new Node(2);  
           Node p4 = new Node(1);  
           head.next = p1;  
           p1.next = p2;  
           p2.next = p3;  
           p3.next = p4;  
           head.random = p4;  
           p1.random = head;  
           p4.random = p3;  
           p2.random = p3;  
           printList(head);  
           Node newHead = cloneUsingHashMap(head);  
           printList(newHead);  
           Node newHead1 = cloneWithoutExtraMemory(head);  
           printList(newHead1);  
      }  
      private static void printList(Node head) {  
           Node t = head;  
           while (t != null) {  
                if (t.random != null) {  
                     System.out.print(t.value + "(" + t.random.value + ") -- ");  
                } else {  
                     System.out.print(t.value + " -- ");  
                }  
                t = t.next;  
           }  
           System.out.print("null");  
           System.out.println();  
      }  
      public static Node cloneNext(Node head) {  
           if (head == null) {  
                return null;  
           }  
           Node newHead = new Node(head.value);  
           cloneNodes.put(head, newHead);  
           // clone recursively  
           newHead.next = cloneNext(head.next);  
           return newHead;  
      }  
      public static Node cloneUsingHashMap(Node head) {  
           Node newHead = cloneNext(head);  
           Node t1 = head;  
           Node t2 = newHead;  
           while (t1 != null) {  
                t2.random = cloneNodes.get(t1.random);  
                t1 = t1.next;  
                t2 = t2.next;  
           }  
           return newHead;  
      }  
      // Without using hashmap or extra memory apart from node memories.  
      public static Node cloneWithoutExtraMemory(Node head) {  
           Node t1 = head;  
           while (t1 != null) {  
                Node newNode = new Node(t1.value);  
                newNode.next = t1.next;  
                t1.next = newNode;  
                t1 = t1.next.next;  
           }  
           // clone random pointers  
           t1 = head;  
           while (t1 != null) {  
                t1.next.random = t1.random;  
                t1 = t1.next.next;  
           }  
           // split clone nodes  
           Node newHead = head.next;  
           t1 = head;  
           Node t2 = head.next;  
           while (t2 != null) {  
                t1.next = t2.next;  
                t2.next = (t1.next == null) ? null : t1.next.next;  
                t1 = t1.next;  
                t2 = t2.next;  
           }  
           return newHead;  
      }  
 }  
 class Node {  
      int value;  
      Node next;  
      Node random;  
      public Node(int value) {  
           this.value = value;  
           this.next = null;  
           this.random = null;  
      }  
 }