Copy List with Random Pointer (Java)

LeetCode

Copy List with Random Pointer

Total Accepted: 4935 Total Submissions: 24214

A linked list is given such that each node contains an additional random pointer which could point to

 any node in the list or null.

Return a deep copy of the list.

Similar problem(Clone Graph)

Solution: 

This is an interesting question. Deep copy a single linked list with only next reference is easy. 

but, the tricky point is how to connect the random reference, we can not know if the node connected by the random reference exists or not when we copy node one by one. So to solve this problem, I think hashmap should be a good solution. With hashMap,do first while loop,  we copy every node in given list and keep them as a <originalNode, copiedNode> pair. then do another while loop connect these copied nodes together.

	/*
	A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
	Return a deep copy of the list.
	*/
	/**
	* Definition for singly-linked list with a random pointer.
	* class RandomListNode {
	* int label;
	* RandomListNode next, random;
	* RandomListNode(int x) { this.label = x; }
	* };
	*/
	public class Solution {
	public RandomListNode copyRandomList(RandomListNode head) {
	if (head==null){
	return null;
	}
	return copy(head);
	}
	private RandomListNode copy(RandomListNode node){
	HashMap<RandomListNode, RandomListNode> hm=new HashMap<RandomListNode, RandomListNode>();
	RandomListNode p=node;
	// copy every node of give list and store it in hashmap
	while(p!=null){
	hm.put(p, new RandomListNode(p.label));
	p=p.next;
	}
	p=node;
	RandomListNode head=null;
	RandomListNode current=null;
	// connect every node with next and random references
	while (p!=null){
	if (head==null){
	head=hm.get(p);
	current=head;
	}
	else{
	current.next=hm.get(p);
	current=current.next;
	}
	if (p.random!=null){
	current.random=hm.get(p.random);
	}
	p=p.next;
	}
	return head;
	}
	}

view raw CopyListWithRandomPointer .java hosted with ❤ by GitHub