怎么在网站上添加地图,网页设计电子版教材,制作网站费怎么做会计科目,游戏推广是做什么的题目内容#xff1a;
138. 随机链表的复制 - 力扣#xff08;LeetCode#xff09; 分析#xff1a;
这道题目#xff0c;第一眼感觉非常乱#xff0c;这是正常的#xff0c;但是我们经过仔细分析示例明白后#xff0c;其实也并不是那么难。现在让我们一起来分析分析…题目内容
138. 随机链表的复制 - 力扣LeetCode 分析
这道题目第一眼感觉非常乱这是正常的但是我们经过仔细分析示例明白后其实也并不是那么难。现在让我们一起来分析分析吧
1.题目要求的是链表的复制那么我们得想我们该怎么做才能很好地进行下去呢
2.是直接把原链表一个一个地移动过来这思路果断不对它还要保持原来的链表不被复制啊.
3.经过观察我们发现13的random指向7。各种穿插的所以我们采用 //复制struct Node* curhead;while(cur){struct Node* copy(struct Node*)malloc(sizeof(struct Node));copy-valcur-val;struct Node*Nextcur-next;cur-nextcopy;copy-nextNext;curNext;}
复制部分
先在每个数复制下来分别放在它的原数字的下一个。即下图 4.接着你看它原链表的那些数字。7的random指向NULL13的random指向7.其他的省略说。7的next指向13。看到这种规律我们试想是不是可以把复制的也弄成这样子就形成了一个独立的复制链表了对吧
连线部分 //连接线curhead;while(cur){struct Node* copycur-next;// struct Node* Nextcur-next-next;if(cur-randomNULL){copy-randomNULL;}else{copy-randomcur-random-next;}curcur-next-next;}
如下图 你看复制完了之后是不是可以直接它复制那部分挪下来它也是不会破坏原链表的这是不是就符合题目要求了对吧
5.完成了这步了之后到了我们一个一个挪的那部分了。
如下图 解释上图 //复制的挪下来恢复原链表struct Node* copyheadNULL,*copytailNULL;curhead; while(cur){struct Node* copycur-next;struct Node* Nextcopy-next; //尾插if(copyheadNULL){copyheadcopytailcopy;}else{copytail-nextcopy;copytailcopytail-next;}
挪动部分
当我们复制完了之后开始挪新的复制链表
1.首先定义一个cur指针指向head头。再定义一个next指针指向cur的下一个方便它随时都能返回找到copy的位置。
2.定义两个指针分别为copyhead和copytail指针放在新的链表那里当作移动工具和最后返回工具
2.接着相当于进行尾插当 第一次时copyhead和copytail都为空时就把copy值直接放到这个指针
3.不为空时就把copy值放到copytail的下一位。 恢复部分
最后恢复原来的链表即去掉它copy的那些数 1.因为我们上面都没有动过cur的位置所以这里就直接使用cur这个指针就行了。
2.把cur的下一个给Next即 把cur的下一个next给给cur的next的next即cur的下下个。 //恢复链表cur-nextNext;curNext;
总代码
/*** Definition for a Node.* struct Node {* int val;* struct Node *next;* struct Node *random;* };*/struct Node* copyRandomList(struct Node* head) {//复制struct Node* curhead;while(cur){struct Node* copy(struct Node*)malloc(sizeof(struct Node));copy-valcur-val;struct Node*Nextcur-next;cur-nextcopy;copy-nextNext;curNext;}//连接线curhead;while(cur){struct Node* copycur-next;// struct Node* Nextcur-next-next;if(cur-randomNULL){copy-randomNULL;}else{copy-randomcur-random-next;}curcur-next-next;}//复制的挪下来恢复原链表struct Node* copyheadNULL,*copytailNULL;curhead; while(cur){struct Node* copycur-next;struct Node* Nextcopy-next; //尾插if(copyheadNULL){copyheadcopytailcopy;}else{copytail-nextcopy;copytailcopytail-next;}//恢复链表cur-nextNext;curNext; }return copyhead;
}
最后特别要注意的是cur的位置要每到一部分都要及时更新变成head。因为它每一部分都在改变不然就会像我一开始那样发现怎么都不正确哇哇哇哇。
每次鸡汤
好啦到了我们的每次鸡汤部分
虽然我每次迈出的那一步都很小但是终究会有那么一天会到达终点的。加油吧青年。
