门户网站是网站优化工作内容

门户网站是,网站优化工作内容,国外cdn,会议专题网站建设报价单若能独立完成本题的思路构建与代码实现#xff0c;说明你对链表的理解已掌握九成。建议先自行尝试解题#xff08;题目链接见下图#xff09;#xff0c;以检验掌握程度。若遇到困难#xff0c;可参考本文提供的详细思路解析和代码实现#xff08;采用C语言#xff09;。…若能独立完成本题的思路构建与代码实现说明你对链表的理解已掌握九成。建议先自行尝试解题题目链接见下图以检验掌握程度。若遇到困难可参考本文提供的详细思路解析和代码实现采用C语言。随机链表的复制链接https://leetcode.cn/problems/copy-list-with-random-pointer本题难点在于如何拷贝randon,怎样才能找到拷贝链表和原链表的关联。解题思路此题可以分三步进行1.拷贝链表的每一个节点拷贝的节点先链接到被拷贝节点的后面节点复制阶段遍历原始链表为每个节点创建拷贝节点将拷贝节点插入到原始节点之后。例如原始链表为A-B-C复制后变为A-A-B-B-C-C。这样我们就将拷贝链表和原链表关联起来对我们后续找链表里的数据至关重要。2.复制随机指针的链接拷贝节点的随机指针指向被拷贝节点随机指针的下一个位置随机指针设置阶段再次遍历链表处理每个拷贝节点的random指针。由于第一步我们将拷贝节点和原连接起来变成A-A-B-B-C-C。由图我们可以看出节点原始节点的random指针指向的节点的下一个节点即为拷贝节点应该指向的位置。若原始节点的random为NULL拷贝节点的random也设为NULL。3.拆解链表把拷贝的链表从原链表中拆解出来链表拆分阶段创建拷贝链表的头指针和尾指针通过遍历将拷贝节点从交错链表中提取出来同时恢复原始链表的连接关系。每次处理将拷贝节点接入拷贝链表尾部并移动原始链表的当前指针。最终返回副本链表的头节点。该算法时间复杂度为O(n)空间复杂度为O(1)不计入返回的深拷贝链表所需空间通过巧妙地利用节点交错排列避免了哈希表的额外空间开销。代码实现struct Node* copyRandomList(struct Node* head) { /* 解题步骤 1. 为每个节点创建副本插入到原节点之后 2. 设置副本节点的random指针 3. 分离原链表和副本链表 */ struct Node* cur head; // 第一步创建并插入副本节点 while(cur) { struct Node* copy (struct Node*)malloc(sizeof(struct Node)); copy-val cur-val; copy-next cur-next; cur-next copy; cur copy-next; } // 第二步设置副本节点的random指针 cur head; while(cur) { struct Node* copy cur-next; copy-random cur-random ? cur-random-next : NULL; cur copy-next; } // 第三步分离两个链表 cur head; struct Node* copyhead NULL, *copytail NULL; while(cur) { struct Node* copy cur-next; cur-next copy-next; if(!copytail) { copyhead copytail copy; } else { copytail-next copy; copytail copy; } cur cur-next; } return copyhead; }如果对你有帮助别忘了一键三连制作不易谢谢支持