邢台手机网站建设,设计师培训心得,赤水市建设局官方网站,怎么建一个购物网站目录一、题目题目链接二、题目分析三、解题思路四、解题步骤4.1 复制结点并链接到对应原节点的后面4.2 处理复制的结点的随机指针random4.3 分离复制的链表结点和原链表结点并重新链接成为链表五、参考代码六、总结一、题目题目链接
题目链接#xff1a;https://…
目录一、题目题目链接二、题目分析三、解题思路四、解题步骤4.1 复制结点并链接到对应原节点的后面4.2 处理复制的结点的随机指针random4.3 分离复制的链表结点和原链表结点并重新链接成为链表五、参考代码六、总结一、题目题目链接
题目链接https://leetcode.cn/problems/copy-list-with-random-pointer/
二、题目分析
这道题是要求我们复制给定的链表给定的链表带有一个随机的指针random该指针random的指向是不确定的方向的并且不能破坏原来的链表结构。
三、解题思路
这道题的思路可以分成三步
1、逐一复制原链表的结点并在复制的同时把复制的结点链接在被复制结点的后面。 2、处理random的指向由于每个复制的结点都在被复制结点的后面所以复制结点的random就在被复制结点random的后一个。最重要的一步 3、分离复制的结点和被复制的结点并依次链接。
四、解题步骤
4.1 复制结点并链接到对应原节点的后面
定义三个指针curcopy和next按照以下方式复制结点并链接起来。当cur为NULL的时候就结束。 复制结束后的效果如下 4.2 处理复制的结点的随机指针random 最核心的步骤是copy-randomcur-random-next,原因参考上面动图。
处理完之后的效果图如下
cur为空就证明已经处理完了。
4.3 分离复制的链表结点和原链表结点并重新链接成为链表 分离后的效果图如下
最后返回copyHead指针即可
五、参考代码
typedef struct Node Node;
struct Node* copyRandomList(struct Node* head)
{if(headNULL){return NULL;}//1.复制链表Node* curhead;while(cur){Node* copy(Node*)malloc(sizeof(Node));copy-valcur-val;Node* nextcur-next;cur-nextcopy;copy-nextnext;curnext;}//2.处理randomcurhead;while(cur){Node* copycur-next;if(cur-random){copy-randomcur-random-next;}else{copy-randomNULL;}curcopy-next;}//3.拆curhead;Node* copyHeadcur-next;while(cur){Node* copycur-next;Node* nextcopy-next;cur-nextnext;if(next){copy-nextnext-next;}curnext;}return copyHead;}六、总结
如果你觉得你链表这块的知识已经学得很扎实了那这道题就是对你链表知识的考验链表的大部分知识都包含在了这道题上面如果能够理清这一题的思路并且做出来那链表这一块的知识基本上就是ok的了这道题还是由一定的难度的而且细节很多你学会了吗喜欢的话点点赞点点关注哟
