LeetCode Q138: Copy List with Random Pointer (hard)

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.

Solution:

The question is not that hard if you really take care of the node that random pointer pointing to. Basically, there are two ways of doing this. First, we pre-allocate memory for node pointed by random pointer and save them to a hash table. When access to each node, check whether the node has been created ahead or not. Another way is much simpler, we do this in two passes scan of the linklist. In first scan, we just build up entire linklist by linking next pointer and hash each new node with its corresponding node in old linklist. In second pass, we take care of nodes pointed by random pointer.

Method 1:

	/**
	* Definition for singly-linked list with a random pointer.
	* struct RandomListNode {
	* int label;
	* RandomListNode *next, *random;
	* RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
	* };
	*/
	class Solution {
	public:
	RandomListNode *copyRandomList(RandomListNode *head) {
	unordered_map<RandomListNode*, RandomListNode*> myMap;
	RandomListNode* p=head;
	RandomListNode* last=NULL;
	RandomListNode* newHead=NULL;
	while(p!=NULL){
	RandomListNode* newNode=new RandomListNode(p->label);
	myMap[p]=newNode;
	if(newHead==NULL)
	newHead=newNode;
	if(last!=NULL)
	last->next=newNode;
	p=p->next;
	last=newNode;
	}
	p=head;
	RandomListNode* pp=newHead;
	while(p!=NULL){
	RandomListNode* tmpOld=p->random;
	RandomListNode* tmpNew=myMap[tmpOld];
	pp->random=tmpNew;
	p=p->next;
	pp=pp->next;
	}
	return newHead;
	}
	};

view raw Q138CopyList.cpp hosted with ❤ by GitHub

Method 2:

	/**
	* Definition for singly-linked list with a random pointer.
	* struct RandomListNode {
	* int label;
	* RandomListNode *next, *random;
	* RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
	* };
	*/
	class Solution {
	public:
	RandomListNode *copyRandomList(RandomListNode *head) {
	unordered_map<RandomListNode*, RandomListNode*> myMap;
	RandomListNode* p=head;
	RandomListNode* last=NULL;
	while(p!=NULL){
	RandomListNode* newNode;
	if(myMap[p]==NULL){
	newNode=new RandomListNode(p->label);
	if(last==NULL)
	last=newNode;
	else
	last->next=newNode;
	myMap[p]=newNode;
	last=newNode;
	}else{
	newNode=myMap[p];
	if(last==NULL)
	last=newNode;
	else
	last->next=newNode;
	myMap[p]=newNode;
	last=newNode;
	}
	RandomListNode* randNode=p->random;
	if(randNode==NULL)
	newNode->random=NULL;
	else{
	if(myMap[p->random]!=NULL){
	newNode->random=myMap[p->random];
	}else{
	myMap[p->random]=new RandomListNode(p->random->label);
	newNode->random=myMap[p->random];
	}
	}
	p=p->next;
	}
	return myMap[head];
	}
	};

view raw Q138-2.cpp hosted with ❤ by GitHub

Round 2 solution:
Using recursion. The solution is very similar to Q133 Clone Graph.

	/**
	* Definition for singly-linked list with a random pointer.
	* struct RandomListNode {
	* int label;
	* RandomListNode *next, *random;
	* RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
	* };
	*/
	class Solution {
	public:
	unordered_map<RandomListNode*, RandomListNode*> hash;
	RandomListNode *copyRandomList(RandomListNode *head) {
	if(head == NULL)
	return head;
	if(hash[head]==NULL){
	hash[head] = new RandomListNode(head->label);
	hash[head]->next = copyRandomList(head->next);
	hash[head]->random = copyRandomList(head->random);
	}
	return hash[head];
	}
	};

view raw Q138Rnd2.cpp hosted with ❤ by GitHub