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.
linked list copy需要copy 当前Node 和 next 和 random两个指针， 怎么能在 遍历一遍Linklist的时候完成两个指针的copy呢， 可以用一个map， map的 key是原Linklist上面的node， value是新的copy的linklist的node, 每次在遍历一个link node的时候，也同时将该node的next 和 random pointer指向的node 进行copy， 并且将新copy的node的next 和 random pointer指向它们， 但是如果这样子去copy的话，需要在每次copy一个新node之前进行check这个node是否之前已经copy过了，即是否已经存在于map中了。 如果已经存在于map中了，就可以直接将指针指向这个已经copy过了的node。
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
//sanity check
if (head == NULL) return head;
map<RandomListNode*, RandomListNode*> copy;
RandomListNode* p = head;
RandomListNode* head1 = new RandomListNode(p->label);
copy[p] = head1;
while (p) {
//make a copy of next pointer
if (p->next != NULL) {
if (copy.find(p->next) == copy.end()) {
RandomListNode* next = new RandomListNode(p->next->label);
copy[p->next] = next;
copy[p]->next = next;
} else {
copy[p]->next = copy[p->next];
}
}
//make a copy of random pointer
if (p->random != NULL) {
if (copy.find(p->random) == copy.end()) {
RandomListNode* random = new RandomListNode(p->random->label);
copy[p->random] = random;
copy[p]->random = random;
} else {
copy[p]->random = copy[p->random];
}
}
p = p->next;
}
return head1;
}
};
updated: do the copy without using hash map
遍历3遍Linkedlist
copy random 和copy next pointer需要分开进行，否则会出错！
/**
* 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 == NULL) return NULL;
RandomListNode* cur = head;
//copy nodes
while (cur) {
RandomListNode* newNode = new RandomListNode(cur->label);
RandomListNode* next = cur->next;
cur->next = newNode;
newNode->next = next;
cur = next;
}
cur = head;
// RandomListNode* rst = head->next;
while (cur) {
RandomListNode* next = cur->next->next;
RandomListNode* curN = cur->next;
//copy random
if (cur->random) {
curN->random = cur->random->next;
}
cur = next;
}
//recover old list and get new list
RandomListNode* pold = head;
RandomListNode* pnew = head->next;
RandomListNode* rst = pnew;
while (pnew->next) {
pold->next = pold->next->next;
pnew->next = pnew->next->next;
pold = pold->next;
pnew = pnew->next;
}
pold->next = NULL;
pnew->next = NULL;
return rst;
}
};
Clone Graph :
这题跟上面的 copy linklist是类似的解法，也是用一个map进行copy和check。 区别在于graph有很多的neighbors，此时需要利用BFS来遍历整个图，在遍历过程中，对图上的每个node进行copy。 具体copy的做法跟上题类似。
class Solution {
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
//sanity check
if (node == NULL) return node;
//use BFS to search the whole graph
map<UndirectedGraphNode *, UndirectedGraphNode *> copy;
queue<UndirectedGraphNode *> explore;
unordered_set<UndirectedGraphNode *> visit;
explore.push(node);
visit.insert(node);
UndirectedGraphNode * newroot = new UndirectedGraphNode(node->label);
copy[node] = newroot;
while (!explore.empty()) {
UndirectedGraphNode * tmp = explore.front();
explore.pop();
for (int i = 0; i < (tmp->neighbors).size(); i++) {
if (visit.find((tmp->neighbors)[i]) == visit.end()) {
visit.insert(tmp->neighbors[i]);
explore.push(tmp->neighbors[i]);
}
if (copy.find(tmp->neighbors[i]) == copy.end()) {
UndirectedGraphNode * nnode = new UndirectedGraphNode((tmp->neighbors)[i]->label);
copy[(tmp->neighbors)[i]] = nnode; //insert into map
copy[tmp]->neighbors.push_back(nnode);
} else {
copy[tmp]->neighbors.push_back(copy[(tmp->neighbors)[i]]);
}
}
}
return newroot;
}
};
BFS其实是一个不太好的答案， 因为它需要的space是要比dfs要高的， 这题用dfs更好一些，下面是dfs的解法：递归和非递归两种形式。
iteration:
class Solution {
private:
void dfs(UndirectedGraphNode *node, unordered_map<UndirectedGraphNode *, UndirectedGraphNode *> &cmap) {
if (node == NULL) return;
cmap[node] = new UndirectedGraphNode(node->label);
for (auto n : node->neighbors) {
if (cmap.find(n) == cmap.end()) {//if the node is not copied copy the node
dfs(n, cmap);
}
cmap[node]->neighbors.push_back(cmap[n]);
}
}
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if (node == NULL) return NULL;
unordered_map<UndirectedGraphNode *, UndirectedGraphNode *> cmap;
dfs(node, cmap);
return cmap[node];
}
};
跟bfs比起来，代码简短并且space 利用较低
这个是目前最好的solution.
class Solution {
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if (node == NULL) return NULL;
stack<UndirectedGraphNode*> buf;
buf.push(node);
unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> cmap;
cmap[node] = new UndirectedGraphNode(node->label);
while (!buf.empty()) {
UndirectedGraphNode * tmp = buf.top();
buf.pop();
for (auto n : tmp->neighbors) {
if (cmap.find(n) == cmap.end()) {
buf.push(n);
cmap[n] = new UndirectedGraphNode(n->label);
}
cmap[tmp]->neighbors.push_back(cmap[n]);
}
}
return cmap[node];
}
};
No comments:
Post a Comment