企业怎么建设网站,建e室内设计网官网全景效果图,直播间网站开发设计,网站服务器的作用和功能有哪些朋友们、伙计们#xff0c;我们又见面了#xff0c;本期来给大家解读一下LeetCode中第138道单链表OJ题#xff0c;如果看完之后对你有一定的启发#xff0c;那么请留下你的三连#xff0c;祝大家心想事成#xff01; 数据结构与算法专栏#xff1a;数据结构与算法 个 人… 朋友们、伙计们我们又见面了本期来给大家解读一下LeetCode中第138道单链表OJ题如果看完之后对你有一定的启发那么请留下你的三连祝大家心想事成 数据结构与算法专栏数据结构与算法 个 人 主 页 stackY、 C 语 言 专 栏C语言从入门到精通 LeetCode--138.复制带随即指针的链表https://leetcode.cn/problems/copy-list-with-random-pointer/description/
目录 1.题目介绍
2.实例演示
3.解题思路
链接拷贝结点
找拷贝节点的random 拆解拷贝链表 1.题目介绍 给你一个长度为 n 的链表每个节点包含一个额外增加的随机指针 random 该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。 小编现在这里向大家袒露心扉一下其实我刚刚看到这个单链表OJ题看了半天连题目都没咋搞明白好不容易看懂了题目介绍可是又不知道该从何下手然后求助各种大佬才慢慢理解然后整理思路在这篇文章中将这道题分享给大家。 2.实例演示 3.解题思路 这道题应该算是单链表OJ题中比较复杂的一道题了主要是比较难理解。题目的主要意思就是要拷贝出与原链表一模一样的一个链表。那么这道题拷贝链表都不是很复杂比较难处理的就是这个随即指针random的指向如果原链表的random指向空那这好说拷贝链表的也指向空但是如果原链表的random指向非空那该如何去找这个random呢在这里呢很多老铁喜欢用random指向的值来比较这种想法可以但是架不住链表中有相同的值那么就有许多老铁用它的random指向的地址来比较这种方法是完全可行的但是呢这种暴力求解的方法往往都不是最优解使用地址来进行比较的话它的时间复杂度是O(N^2)效率也是不太行。所以我们需要寻求更优解。 这道题的解题思路我分为了三个步骤 1. 链接拷贝结点 将拷贝结点插入到原结点的后面。 2. 找拷贝节点的random 通过原链表来控制拷贝结点的随机指针random。 3. 拆解拷贝链表 将拷贝结点拆下来依次尾插组成新的链表然后恢复原链表。 接下来我们一步一步来进行解题 链接拷贝结点 我们可以将拷贝结点链接在原结点的后面这种方法比较巧妙有助于我们找随即指针random。 先创建拷贝节点然后遍历原链表然后保存头节点的下一个结点改变指向将拷贝节点插入到原结点的后面。 图示 代码演示 /*** Definition for a Node.* struct Node {* int val;* struct Node *next;* struct Node *random;* };*/struct Node* copyRandomList(struct Node* head) {struct Node* cur head;//1.链接拷贝节点while(cur){//创建拷贝结点struct Node* copy (struct Node*)malloc(sizeof(struct Node));copy-val cur-val;//保存头指针的下一个结点struct Node* curNext cur-next;//链接cur-next copy;copy-next curNext;cur curNext;}//......
} 找拷贝节点的random 当我们将拷贝结点链接在原结点的后面时我们需要找拷贝结点的随机指针random这里可以分为两种情况 1. 如果原结点的random是空那么直接将拷贝结点的random置为空即可。 2. 若不为空那么就需要观察一下这个链表拷贝结点的random指针指向的就是原结点的random指向的结点的next结点 copy - random cur - random - next; 因为我们将拷贝结点链接在了原结点的后面那么原结点的random指向的结点的next结点就是拷贝结点要找的random。我们依旧遍历整个链表然后将拷贝节点的随机指针链接。 图示 代码演示 /*** Definition for a Node.* struct Node {* int val;* struct Node *next;* struct Node *random;* };*/struct Node* copyRandomList(struct Node* head) {struct Node* cur head;//1.链接拷贝节点while(cur){//创建拷贝结点struct Node* copy (struct Node*)malloc(sizeof(struct Node));copy-val cur-val;//保存头指针的下一个结点struct Node* curNext cur-next;//链接cur-next copy;copy-next curNext;cur curNext;}//2.找拷贝节点的random //重新返回头cur head;while(cur){//找拷贝结点struct Node* copy cur-next;//找下一个结点struct Node* next copy-next;//链接拷贝节点的随机指针randomif(cur-random NULL){copy-random NULL;}else{copy-random cur-random-next;}//遍历cur next;}//......
} 拆解拷贝链表 我们找到了拷贝链表之后呢需要将这些拷贝的结点组成一个新的链表这就需要将这些拷贝结点依次进行尾插然后再将原链表恢复。这就比较简单了 图示 完整代码演示 /*** Definition for a Node.* struct Node {* int val;* struct Node *next;* struct Node *random;* };*/struct Node* copyRandomList(struct Node* head) {struct Node* cur head;//1.链接拷贝节点while(cur){//创建拷贝结点struct Node* copy (struct Node*)malloc(sizeof(struct Node));copy-val cur-val;//保存头指针的下一个结点struct Node* curNext cur-next;//链接cur-next copy;copy-next curNext;cur curNext;}//2.找拷贝节点的random //重新返回头cur head;while(cur){//找拷贝结点struct Node* copy cur-next;//找下一个结点struct Node* next copy-next;//链接拷贝节点的随机指针randomif(cur-random NULL){copy-random NULL;}else{copy-random cur-random-next;}//遍历cur next;}//3.拆解拷贝结点恢复原链表//重新返回头cur head;//创建新的链表struct Node* copyHead NULL;struct Node* copyTail NULL;while(cur){//找拷贝结点struct Node* copy cur-next;//找下一个结点struct Node* next copy-next;//尾插拷贝节点构成新的链表if(copyTail NULL){copyHead copyTail copy;}else{copyTail-next copy;copyTail copyTail-next;}//恢复原链表cur-next next;cur next;}return copyHead;} 朋友们、伙计们美好的时光总是短暂的我们本期的的分享就到此结束最后看完别忘了留下你们弥足珍贵的三连喔感谢大家的支持
