企业网站推广计划书,手机关键词seo排名优化,网站建设外包网站,深圳网站定制公司前言: #x1f4a5;#x1f388;个人主页:Dream_Chaser#xff5e; #x1f388;#x1f4a5; ✨✨刷题专栏:http://t.csdn.cn/UlvTc ⛳⛳本篇内容:力扣上链表OJ题目 目录
leetcode138. 复制带随机指针的链表
1. 问题描述
2.代码思路:
2.1拷贝节点插入到…前言: 个人主页:Dream_Chaser ✨✨刷题专栏:http://t.csdn.cn/UlvTc ⛳⛳本篇内容:力扣上链表OJ题目 目录
leetcode138. 复制带随机指针的链表
1. 问题描述
2.代码思路:
2.1拷贝节点插入到原节点的后面
2.2控制拷贝节点的random
2.3拷贝节点解下来尾插组成拷贝链表恢复原链表 leetcode138. 复制带随机指针的链表 来源:138. 复制带随机指针的链表 - 力扣LeetCode 1. 问题描述 给你一个长度为 n 的链表每个节点包含一个额外增加的随机指针 random 该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不 应指向原链表中的节点 。 例如如果原链表中有 X 和 Y 两个节点其中 X.random -- Y 。那么在复制链表中对应的两个节点 x 和 y 同样有 x.random -- y 。 返回复制链表的头节点。 题解接口: struct Node* copyRandomList(struct Node* head) {} 2.代码思路:
2.1拷贝节点插入到原节点的后面 复制节点遍历原链表对于每个节点创建一个副本节点并将其插入到原节点的后面。 我们一步一步分解来做首先malloc一个新的节点然后让copy指针接收让原链表第一个节点里面的val值赋值给新malloc出来的链表。 最后记得将curnext让cur指向next,循环条件是cur不为NULL再次回到循环重复①②③④⑤⑥⑦的步骤 这是链表的最后情况。 2.2控制拷贝节点的random 设置random指针遍历链表对于每个原节点设置对应副本节点的random指针。 如果原节点的random指针为NULL则副本节点的random指针也设置为NULL否则副本节点的random指针设置为原节点的random指针指向的节点的副本节点。 分解动作 ①把cur指针重新指向原链表头节点(head) ②进入while循环条件是cur不为NULL,定义一个新指针copy然后让其指向新组成的链表头节点的下一个节点cur-next ③ 如果原链表的random域指向的地址为NULL那么新节点的random域指向NULL 如果原链表的random域指向的地址不为NULL那么此时将此时cur-random-next的地址赋值给新节点的copy-random ④将copy-next赋值给cur 循环①②③④步,结束条件是cur指向NULL 这是最终情况. 2.3拷贝节点解下来尾插组成拷贝链表恢复原链表 分离链表遍历合并后的链表将链表分离为原链表和副本链表。同时恢复原链表的next指针使其指向原链表的下一个节点同时构建副本链表通过尾插法将副本节点依次添加到副本链表的末尾。 尾插: 恢复链表 循环条件依然是cur不为NULL当cur指向NULL,循环结束直接返回副本链表的头节点copyHead 代码实现: struct Node* copyRandomList(struct Node* head) {//1.拷贝节点插入在原节点的后面struct Node* curhead;while(cur){struct Node* copy(struct Node*)malloc(sizeof(struct Node));copy-valcur-val;struct Node* next cur-next;//插入cur-nextcopy;copy-nextnext;curnext;}//2.控制拷贝节点的randomcurhead;while(cur){struct Node* copycur-next;if(cur-random NULL){copy-randomNULL;}else{copy-randomcur-random-next;}cur copy-next;}// 3、拷贝节点解下来尾插组成拷贝链表恢复原链表struct Node*copyHead NULL,*copyTailNULL;curhead;while(cur){struct Node* copycur-next;struct Node* nextcopy-next;//尾插if(copyTail NULL){copyHead copyTailcopy;}else{copyTail-nextcopy;copyTailcopyTail-next;}//恢复原链表cur-nextnext;cur next;}return copyHead;
} 执行: 文章讲解到此结束如有错误,欢迎指正 感谢支持
