初见写法 + 优化写法
建议直接看优化写法,初见写法虽然能通过但是代码写的惨不忍睹
初见代码(一塌糊涂)
class Solution {
public:
Node* copyRandomList(Node* head) {
if(!head)return head;
Node* dummy = new Node(-1);
Node* p = dummy, *q = head;
int cnt = 0;
while(q){
p->next = new Node(q->val);
q = q->next;
p = p->next;
}
q = head;
unordered_map<int, int> dict;
int idx = 0;
while(q){
Node* temp = head;
while(temp && q->random && temp != q->random){
idx ++;
temp = temp->next;
}
if(!q->random)dict[cnt] = -1;
else dict[cnt] = idx;
idx = 0;
q = q->next;
cnt ++ ;
}
p = dummy->next;
unordered_map<int, Node*> got;
cnt = 0;
while(p){
got[cnt ++ ] = p;
p = p->next;
}
p = dummy->next;
cnt = 0;
while(p){
if(dict[cnt] == -1)
p->random = NULL;
else
p->random = got[dict[cnt]];
cnt ++ ;
p = p->next;
}
return dummy->next;
}
};
优化代码
class Solution {
public:
Node* copyRandomList(Node* head) {
if(!head)return head;
Node* dummy = new Node(-1);
Node* p = dummy, *q = head;
unordered_map<Node*, Node*> dict;//其实只需一个hash map
//就可以将原链表和新链表的节点一一形成键值对
//这里反映出对哈希表理解的还不够透彻
while(q){
p->next = new Node(q->val);
dict[q] = p->next;
q = q->next;
p = p->next;
}
p = dummy->next, q = head;
while(p){
p->random = dict[q->random];
p = p->next;
q = q->next;
}
return dummy->next;
}
};