Leetcode 138. Copy List with Random Pointer

2019-11-14 08:43:21

字體：大中小

來源：轉載

供稿：網友

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.

s思路： 1. 如果正常的鏈表，要拷貝就容易：從左往右訪問，遇到一個節點，就產生一個新節點放在新鏈表尾部。這道題的鏈表就不“正?！保總€節點還可能指向前面已經生成的節點或后面還沒產生的節點。如果第一遍先不管random指針，先按照正常鏈表產生；然后再處理random指針。問題是：舊鏈表之間的random指針如何復制到新鏈表中去？這個方法，把新舊鏈表完全獨立開來，舊鏈表的random指針就無法復制到新鏈表了。 2. 上面的方法新建一個鏈表，新舊鏈表沒有任何聯系，所以導致raondom指針無法復制到新的鏈表。參考了答案，不得不說被shock了。如下圖，新建的鏈表先放在舊鏈表的每個節點后面，而不是單獨另起爐灶搞個新攤子，每個新節點都跟在原來節點屁股后面，這樣新舊鏈表關系就非常密切，而不是割裂開來！等所有的新節點都放好后，就很容易把就鏈表的random指針復制到新鏈表，最后刪除老節點即可！

這里寫圖片描述 3. 如果說從頭開始新建一個鏈表將完全和舊的鏈表沒有關系，那么這種方式，把每個新的節點插入在舊鏈表中，就可以完全利用新舊之間的關系。我們還可以說，舊鏈表在復制的過程中，充當了scaffold的功能。新舊的交叉起來，就像修房子時，房子是被腳手架支撐起來的，修房子的過程，就是圍繞腳手架修，腳手架和房子相互穿插，而不是完全獨立。等房子修好后，再把腳手架拆除。回到這個問題，房子就是要的新的鏈表，而腳手腳就是舊的鏈表。這里寫圖片描述 4. 還有一點想說的是，這種把多個過程交叉而不是完全割裂的做法才是問題的本來面貌，其他做法只是試圖簡化，最終看不到問題的全貌。所以做題的時候，一定要搞清楚，什么是問題的原貌，什么是人為的簡化！突然想起愛因斯坦的一句名言：我們應該使問題簡單到本來面貌即可，而不是試圖把復雜問題簡化。深有體會啊！

"Everything should be made as simple as possible, but not simpler."http://方法1：把舊鏈表當成新鏈表的scaffold!class Solution {public: RandomListNode *copyRandomList(RandomListNode *head) { // if(!head) return head; RandomListNode* p=head; while(p){ RandomListNode* node=new RandomListNode(p->label); node->next=p->next; p->next=node; p=node->next; } p=head; while(p){ p->next->random=p->random?p->random->next:NULL;//千年老bug，不容易重視：不能保證p->random存在，就要添加保護措施，不能“裸奔” p=p->next->next; } RandomListNode* newhead=head->next; p=head->next; while(p){//把新舊鏈表分開，舊鏈表重新組裝成原來的樣子，而不是隨意扔掉！ head->next=p->next; head=head->next; p->next=head?head->next:NULL;//千年老bug，不容易重視：不能保證head存在，就要添加保護措施，不能“裸奔” p=p->next; } return newhead; }};

上一篇：【POJ 2528】Mayor's posters

下一篇：P1074 靶形數獨（TLE 75）