28. Clone a linked list with next and random pointer

28. Clone a linked list with next and random pointer

Problem link :- click here

package Linked_List;

import java.util.HashMap;

class Node4 
{
	int data;
	Node4 next;
	Node4 random;
	
	Node4()
	{
		this.next = null;
		this.random = null;
	}
	Node4(int a)
	{
		this.data = a;
		this.next = null;
		this.random = null;
	}
}

class LinkedList4
{
	Node4 head;
	
	public void push(int a)
	{
		Node4 node = new Node4(a);
		
		if(this.head == null)
			this.head = node;
		else
		{
			Node4 temp = this.head;
			for(temp=this.head; temp.next!=null; temp=temp.next)
			{}
			temp.next = node;
		}
	}
	
	public void printNext()
	{
		Node4 temp = this.head;
		for(temp=this.head; temp!=null; temp=temp.next)
			System.out.print(temp.data + "-> ");
		System.out.println("null");
	}
	
	public void printRandomPairs()
	{
		Node4 temp = this.head;
		for(temp=this.head; temp!=null; temp=temp.next)
		{
			if(temp.random != null)
				System.out.print("{" + temp.data + ", " + temp.random.data + "}\t");
		}
		System.out.println();
	}
}

public class LinkedList__28
{
	/*
	 	We are given a special linked list with N nodes where each node has a next pointer
	 	pointing to its next node. You are also given M random pointers, where you will be
	 	given M number of pairs denoting two nodes a and b i.e., a->random = b.
	 	
	 	Brute force :- 
	 		we need a Hash map of node and node 
	 	1 -> we will iterate through the linked list and create a new node of same data
	 		and add those nodes to the hash map
	 	2 -> we will once again iterate through the linked list and now we will link the 
	 		copy node that we added in the hash map
	 */
	
	static Node4 cloneLinkedListBruteForce(LinkedList4 list)
	{
		HashMap<Node4, Node4> map = new HashMap<>();
		
		//step 1 :-
		Node4 temp = list.head;
		for(temp=list.head; temp!=null; temp=temp.next)
		{
			Node4 node = new Node4(temp.data);
			map.put(temp, node);
		}
		
		//step 2 :- 
		temp = list.head;
		for(temp=list.head; temp!=null; temp=temp.next)
		{
			Node4 node = map.get(temp);
			Node4 next = map.get(temp.next);
			
			node.next = next;
		}
		
		temp = list.head;
		for(temp=list.head; temp!=null; temp=temp.next)
		{
			Node4 node = map.get(temp);
			Node4 random = map.get(temp.random);
			
			node.random = random;
		}
		
		temp = list.head;
		return map.get(temp);
	}
	
	/*
	 	We can optimize the solution, we can do this job without using hash map.
	 	
	 	Why we used the hash map in the above solution because we have not linked 
	 	them and we wanted to store them in some place where we could find them 
	 	easily.
	 	So we placed them with the original nodes so if we know the original node 
	 	we could find the copy node easily.
	 	
	 	Lets do the same thing here also but we will not use any extra space.
	 		Instead of placing node in the hash map lets make some space in the linked 
	 		list. 
	 	Lets place the copy node to the next of the original node and 
	 		the next of copy node will contain the next original node.
	 		
	 		original ->  a      b        c        d        e
	 		copy -> 	a  a`  b  b`  c  c`  d  d`  e  e`
	 		
	 	a` b` c` d` e` 	are the copy nodes, now we can access them easily and no need
	 					of extra space.
	 					
	 	The remaining steps will be as it is.
	 */
	
	static Node4 cloneLinkedListOptimized(LinkedList4 list)
	{
		//step 1 :-
		Node4 temp = list.head;
		while(temp!=null)
		{
			Node4 node = new Node4(temp.data);
			
			//inserting node b\w    temp   &    temp.next
			Node4 next = temp.next;
			temp.next = node;
			node.next = next;
			
			temp = temp.next.next;
		}
		
		//step 2 :- Initiating the random link first
		//			because if we break the next we cannot link the random pointer
		temp = list.head;
		while(temp != null)
		{
			/*
			 	a  a`  b  b`  c  c`  d  d`  e  e`
			 	
			 	lets assume that         a.random    is     d
			 	then we have link       a`.random   to   d`
			 	so   a.next.random =  a.random.next
			 */
			temp.next.random = temp.random.next;
			
			temp = temp.next.next;
		}
		
		//step 3 :- now we are breaking the next so we must need a pointer to hold the
		//		  head of the copy linked list
		temp = list.head;
		Node4 head = temp.next;
		Node4 node = head;                  //this is for iteration
		
		while(temp != null)
		{
			Node4 ori_next = temp.next.next;
			node.next = (node.next != null) ? node.next.next : null;
			
			temp.next = ori_next;
			
			//updating temp and node
			temp = temp.next;
			node = node.next;
		}
		
		return head;
	}
	
	public static void main(String[] args)
	{
		LinkedList4 list = new LinkedList4();
		list.push(1);
		list.push(2);
		list.push(3);
		list.push(4);
		list.push(5);
		
		//creating random pairs 
		list.head.random = list.head.next.next;
		list.head.next.random = list.head;
		list.head.next.next.random = list.head.next.next.next.next;
		list.head.next.next.next.random = list.head.next.next;
		list.head.next.next.next.next.random = list.head.next;
		
		System.out.println("Original Linked list : ");
		list.printNext();
		list.printRandomPairs();
		
		LinkedList4 list2 = new LinkedList4();
		list2.head = cloneLinkedListOptimized(list);
		System.out.println("\nClone Linked list : ");
		list2.printNext();
		list2.printRandomPairs();
	}

}

Time complexity :- O(n)
Space complexity :- O(1)