赞
踩
https://leetcode-cn.com/problems/copy-list-with-random-pointer/
思路一:首先忽略 r a n d o m random random指针,遍历给定链表 h 1 h_1 h1,同时建立出它的深拷贝 h 2 h_2 h2,并建立从 h 1 h_1 h1到 h 2 h_2 h2的映射。然后我们再次遍历链表 h 1 h_1 h1,有了映射关系,就可以修改 r a n d o m random 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) { if(!head) return head; unordered_map<Node*,Node*> m; Node myHead(0); Node *cur1=&myHead,*cur2=head; while(cur2){ cur1->next=new Node(cur2->val); cur1=cur1->next; m[cur2]=cur1; cur2=cur2->next; } cur1=myHead.next; cur2=head; while(cur2){ cur1->random=m[cur2->random]; cur1=cur1->next; cur2=cur2->next; } return myHead.next; } };
思路二:和思路一一样,但是我们可以一步到位,无需遍历 h 1 h_1 h1两遍。
/* // 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) return head; unordered_map<Node*,Node*> m; Node myHead(0); Node *cur1=&myHead,*cur2=head; while(cur2){ if(m.find(cur2)!=m.end()) cur1->next=m[cur2]; else{ cur1->next=new Node(cur2->val); m[cur2]=cur1->next; } cur1=cur1->next; if(!cur2->random){ cur2=cur2->next; continue; } //处理random指针 if(m.find(cur2->random)!=m.end()) cur1->random=m[cur2->random]; else{ cur1->random=new Node(cur2->random->val); m[cur2->random]=cur1->random; } cur2=cur2->next; } return myHead.next; } };
思路三:这个思路相当巧妙,可以做到 O ( 1 ) O(1) O(1)的空间复杂度。先遍历一遍 h 1 h_1 h1,每个节点进行自我复制,并将其连接到自己后面,比如: A − > B − > C A->B->C A−>B−>C,经过这次操作后就变成了 A − > A − > B − > B − > C − > C A->A->B->B->C->C A−>A−>B−>B−>C−>C;再遍历一遍 h 1 h_1 h1,这个时候处理 r a n d o m random random指针就比较容易了;最后遍历一遍 h 1 h_1 h1,将其拆分成两个链表即可。
/* // 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) return head; Node *cur=head,*nxt,*tmp; //复制自身并连接在自己后面 while(cur){ nxt=cur->next; cur->next=new Node(cur->val); cur->next->next=nxt; cur=nxt; } cur=head; //处理random指针 while(cur){ nxt=cur->next; tmp=nxt->next; if(cur->random) nxt->random=cur->random->next; cur=tmp; } Node ans(0),*pre=&ans; cur=head; while(cur){ nxt=cur->next; tmp=nxt->next; cur->next=tmp; cur=tmp; pre->next=nxt; pre=nxt; } return ans.next; } };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。