[LeetCode] 138. Copy List with Random Pointer

轉自LeetCode

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>

這題和 Clone Graph 類似，也是 deep copy 的題目

這次要處理的是 link list 中，每個 node 都還有一個 random pointer

random pointer 可以指向任何在 link list 裡的 node，或是 NULL

首先看 recursive 的解法，想法如下

• 先把整個 list copy 完，並在過程中，用 HashMap 記錄每個 node 對應的新 node

• 再處理 random pointer 的部分，如果有值，利用 HashMap 去找對應的 node(O(1))，是 NULL 就直接回傳 NULL

code 如下

	/**
	* 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 {
	private:
	unordered_map<RandomListNode *, RandomListNode *> nodeMap;
	public:
	RandomListNode *copyRandomList(RandomListNode *head) {
	return deepCopy(head, false);
	}
	RandomListNode *deepCopy(RandomListNode *node,const bool &isRandom) {
	if(!node) {
	return NULL;
	}
	else if(isRandom) {
	return nodeMap[node];
	}
	RandomListNode *newNode = new RandomListNode(node->label);
	//>> newNode is the copy of node
	nodeMap[node] = newNode;
	//>> process next pointer first
	newNode->next = deepCopy(node->next, false);
	//>> process random pointer
	newNode->random = deepCopy(node->random, true);
	return newNode;
	}
	};

view raw deepCopyLinkListWithRandomPointer_1.cpp hosted with ❤ by GitHub

也可以改寫成 iterative，想法同上

code 如下

	/**
	* 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) {
	if(!head) {
	return NULL;
	}
	RandomListNode *ans = new RandomListNode(head->label);
	RandomListNode *ansCur = ans;
	RandomListNode *cur = head->next;
	unordered_map<RandomListNode *, RandomListNode *> nodeMap;
	nodeMap[head] = ans;
	//>> copy list first
	while(cur) {
	ansCur->next = new RandomListNode(cur->label);
	nodeMap[cur] = ansCur->next;
	cur = cur->next;
	ansCur = ansCur->next;
	}
	//>> copy random pointer
	cur = head;
	ansCur = ans;
	while(cur) {
	ansCur->random = (cur->random) ? nodeMap[cur->random] : NULL;
	cur = cur->next;
	ansCur = ansCur->next;
	}
	return ans;
	}
	};

view raw deepCopyLinkListWithRandomPointer_2.cpp hosted with ❤ by GitHub

在網路上也看到一個神解

想法如下(圖解請參考這裡)

• 先複製整個 list，每個複製的 node 都插在原 node 的後頭

• 複製 random pointer

• 將原 node 和複製的 node 分解成兩個 link list

code 如下

	/**
	* 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) {
	if(!head) {
	return NULL;
	}
	//>> copy each node and then insert to original list
	RandomListNode *cur = head;
	while(cur) {
	RandomListNode *copyNode = new RandomListNode(cur->label);
	copyNode->next = cur->next;
	cur->next = copyNode;
	cur = copyNode->next;
	}
	//>> copy random pointer
	cur = head;
	while(cur) {
	if(cur->random) {
	//>> next pointer of each node points to the copy of this node
	cur->next->random = cur->random->next;
	}
	cur = cur->next->next;
	}
	//>> decouple two link lists
	RandomListNode *ans = head->next;
	RandomListNode *ansCur = ans;
	cur = head;
	while(cur) {
	cur->next = ansCur->next;
	if(ansCur->next) {
	ansCur->next = ansCur->next->next;
	}
	cur = cur->next;
	ansCur = ansCur->next;
	}
	return ans;
	}
	};

view raw deepCopyLinkListWithRandomPointer_3.cpp hosted with ❤ by GitHub