珠海网站空间注册,哪个软件是网页编辑软件,wordpress厨房家居主题,WordPress中英文旅游模板#x1f525;个人主页#xff1a;草莓熊Lotso #x1f3ac;作者简介#xff1a;C研发方向学习者 #x1f4d6;个人专栏#xff1a; 《C语言》 《数据结构与算法》《C语言刷题集》《Leetcode刷题指南》 ⭐️人生格言#xff1a;生活是默默的坚持#xff0c;毅力是永久的… 个人主页草莓熊Lotso 作者简介C研发方向学习者 个人专栏 《C语言》 《数据结构与算法》《C语言刷题集》《Leetcode刷题指南》 ⭐️人生格言生活是默默的坚持毅力是永久的享受。 前言 随着编程相关知识点的学习我们LeetCode的刷题也不能落下。在前面我们也接触到了洛谷和牛客这两个刷题网站但是博主一直都在推荐大家使用力扣是因为力扣的判题严谨且大部分都是接口型题目与面试中的笔试题也更加贴合。那么还是老样子博主会为大家提供我自己的思路和代码但是算法题的解法肯定不止一个欢迎大家一起交流和讨论。 目录
链表的随机复制
解题过程
代码演示 链表的随机复制 题目链接138. 随机链表的复制 - 力扣LeetCode 题目描述 题目示例 思路在原链表基础上拷贝节点置random指针断开新旧链表
解题过程
1.我们首先需要了解一下什么是浅拷贝什么是深拷贝 浅拷贝Shallow Copy
• 定义仅复制变量本身的值对于指针类型的成员只复制指针的地址而不复制指针所指向的内存内容。
• 特点
◦ 拷贝后原变量和新变量中的指针指向同一块内存空间。
◦ 实现简单通常通过直接赋值如运算符或memcpy等函数完成。
◦ 风险当其中一个指针释放内存后另一个指针会变成野指针再次操作可能导致内存错误如重复释放、访问已释放内存。
深拷贝Deep Copy
• 定义不仅复制变量本身的值对于指针类型的成员会先为新变量的指针分配新的内存空间再将原指针指向的内容复制到新内存中。
• 特点
◦ 拷贝后原变量和新变量中的指针指向各自独立的内存空间两者互不影响。
◦ 需要手动实现通常通过自定义函数完成需显式分配内存并复制内容。
◦ 安全性高避免了浅拷贝的内存冲突问题但实现相对复杂且会额外消耗内存。
2. 在原链表的基础上拷贝节点 3.置random指针
一定要记住copy-randompcur-random-next 4.断开新旧链表 时间复杂度O(N)
代码演示
/*** Definition for a Node.* struct Node {* int val;* struct Node *next;* struct Node *random;* };*/
typedef struct Node Node;
Node* BuyNode(int x)
{Node*newnode(Node*)malloc(sizeof(Node));newnode-valx;newnode-nextnewnode-randomNULL;return newnode;
}
void InsertaList(Node*head)
{Node*pcurhead;while(pcur){Node*newnodeBuyNode(pcur-val);Node*nextpcur-next;pcur-nextnewnode;newnode-nextnext;pcurnext;}
}
void SetRandom(Node*head)
{Node*pcurhead;while(pcur){Node*copypcur-next;if(pcur-random)copy-randompcur-random-next;pcurcopy-next;}
}
struct Node* copyRandomList(struct Node* head) {if(headNULL){return head;}//拷贝原链表的节点并插入原链表中InsertaList(head);//设置randomSetRandom(head);//断开新的链表Node*pcurhead;Node*copyhead,*copytail;copyheadcopytailpcur-next;while(copytail-next){pcurcopytail-next;copytail-nextpcur-next;copytailcopytail-next;}return copyhead;
} 这里需要特别注意一下如果为空特殊处理不然运行会有问题 往期回顾
【数据结构初阶】--双向链表(一)
【数据结构初阶】--双向链表(二)
结语本篇文章就到此结束了《LetetCode刷题指南》中的题目比起之间的C语言刷题集中的题目肯定会更加复杂一些。而且题目形式也不一样大家需要注意一下。如果文章对你有帮助的话欢迎评论点赞收藏加关注感谢大家的支持
