Clone a linked list with next and random pointer.

Clone a linked list with next and random pointer.

Solution 1 : By using Map, In first traversing of list clone the entire list into map.
And now in second traverse of list update the next and random pointers of the clone list.
Space: O(n),
Time : O(n)

Solution 2 : While traversing the list insert the clone node after its original node, by this we have a behavior of map.

Note : But this approach is not recommended in real, because in run time we are not suppose to modify the original list.
Now we have something like this..

Original List : a–>b–>c–>d–>#
While Cloning : a–>a’–>b–>b’–>c–>c’–>d–>d’–#

Again traverse the list, now link a’–>b’–>c’–>d’–># and also update the random pointer,
Suppose a–random is-c->
Then in above cloning step, a–random–>c and its clone node will be a–random–>c–>c’.

package com.rrohit.algo.linkedlist;

import java.util.HashMap;
import java.util.Map;

/*
 *@author : rrohit
 */

public class DeepCopy {

	private RandomNode head;
	private RandomNode tail;
	public DeepCopy(){
		head = null;
		tail = null;
	}

	public void add(int data){
		this.add(new RandomNode(data));
	}

	public void add(RandomNode node){
		if (this.head == null) {
			head = node;
			tail = head;
		}else {
			tail.next = node;
			tail = node;
		}
	}

	public void display(RandomNode head){
		RandomNode current = head;
		while(current != null){
			System.out.print("["+current.data+"]-->[Random-"+current.random.data+",Next-->");
			current = current.next;
		}
		System.out.print("null");
	}

	public RandomNode deepCopyUsingHashMap(){
		if (this.head == null){
			return null;
		}

		Map<RandomNode, RandomNode> map = new HashMap<RandomNode, RandomNode>();
		RandomNode current = head;
		RandomNode newNode = null;
		while(current != null){
			newNode = new RandomNode(current.data);
			map.put(current, newNode);
			current = current.next;
		}
		current = head;
		while (current != null){
			newNode = map.get(current);
			newNode.next = map.get(current.next);
			newNode.random = map.get(current.random);
			newNode = newNode.next;
			current = current.next;
		}
		return map.get(head);
	}

	/*
	 * In constant space, not more then required to clone linked list
	 * But this is not the right approach in run time because we are destroying the original linked list.
	 * if anybody wants to access original linked list then that is gone.
	 * Can't revert back the original till cloning completes because some node random can pint back to previous node as well.
	 */
	public RandomNode deepCopyInPlace() {
		if (this.head == null){
			return null;
		}

		RandomNode current = head;
		RandomNode newNode, temp;

		while (current != null){
			temp = current.next;
			newNode = new RandomNode(current.data);
			current.next = newNode;
			newNode.next = temp;
			current = temp;
		}
		current = head;
		RandomNode head1 = null, clone=null;
		while (current != null){
			temp = current.next;
			if (head1 == null){
				head1 = temp;
				head1.random = current.random.next;
				clone = head1;
			}else{
				clone.next = temp;
				clone = clone.next;
				clone.random = current.random.next;
			}
			current = temp.next;
		}
		clone.next = null;
		return head1;
	}

	public class RandomNode{
		int data;
		RandomNode next;
		RandomNode random;
		public RandomNode(){}
		public RandomNode(int data) {
			this.random = null;
			this.next = null;
			this.data = data;
		}
	}

	public static void main(String[] args) {
		DeepCopy dp = new DeepCopy();
		DeepCopy.RandomNode n1 = dp.new RandomNode(1);
		DeepCopy.RandomNode n2 = dp.new RandomNode(2);
		DeepCopy.RandomNode n3 = dp.new RandomNode(3);
		DeepCopy.RandomNode n4 = dp.new RandomNode(4);
		DeepCopy.RandomNode n5 = dp.new RandomNode(5);
		DeepCopy.RandomNode n6 = dp.new RandomNode(6);
		DeepCopy.RandomNode n7 = dp.new RandomNode(7);
		dp.add(n1);
		dp.add(n2);
		dp.add(n3);
		dp.add(n4);
		dp.add(n5);
		dp.add(n6);
		dp.add(n7);
		n1.random=n3;
		n2.random=n4;
		n3.random=n5;
		n4.random=n6;
		n5.random=n7;
		n6.random=n3;
		n7.random=n2;
		dp.display(dp.head);
		System.out.println("\n After Cloning");
//		RandomNode clone = dp.deepCopyUsingHashMap();
		RandomNode clone = dp.deepCopyInPlace();
		dp.display(clone);
	}

}