Leetcode 138. Copy List with Random Pointer

2019-11-11 07:08:17

字体：大中小

来源：转载

供稿：网友

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."//方法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; }};

上一篇：C#集成第三方控件devexpress 15.2安装说明

下一篇：HDU - 3634 离散化