方法一,先把原链表复制一份,在连接next,再连接random
原节点的random是新节点的next的random。题解里 https://leetcode-cn.com/problems/copy-list-with-random-pointer/solution/liang-chong-shi-xian-tu-jie-138-fu-zhi-dai-sui-ji-/ 非常清晰
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
if( head == nullptr) return nullptr;
Node *cur = head;
while(cur){ //复制新节点
Node * newNode = new Node(cur->val);
newNode->next = cur->next;
cur->next = newNode;
cur = cur->next->next;
}
cur = head;
while(cur){ //建立random关系
if(cur->random == nullptr) cur->next->random = nullptr;
else {
cur->next->random = cur->random->next;
}
cur = cur->next->next;
}
//将两个子链分开
Node *dumpy = new Node(-1);
Node *cur_new = dumpy;
Node *cur_old = head;
while(cur_old){
Node * next = cur_old->next->next;
cur_new->next = cur_old->next;
cur_new = cur_old->next;
cur_old->next = next;
cur_old = cur_old->next;
}
return dumpy->next;
}
};
哈希 为什么不能放到一次循环里,又为什么是p->next not p->random 呢?
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
unordered_map<Node*,Node*> mp;
mp[nullptr] = nullptr;
auto p = head;
while(p){
mp[p] = new Node(p->val);
p = p->next;
}
p = head;
while(p){
mp[p]->next = mp[p->next];
p = p->next;
}
p = head;
while(p){
mp[p]->random = mp[p->random];
p = p->next;
}
return mp[head];
}
};