美食网站开发环境,移动宽带,阿里云官网入口,做好的网站如何上线目录 1.随机链表的复制 1.2题目描述 1.3题目分析 1.4解题#xff1a; 2.顺序表和链表对比 2.1cpu高速缓存利用率 3.结语 1.随机链表的复制
一个长度为 n 的链表#xff0c;每个节点包含一个额外增加的随机指针 random 该指针可以指向链表中的任何节点或空节点。 1.2题目描…
目录 1.随机链表的复制 1.2题目描述 1.3题目分析 1.4解题 2.顺序表和链表对比 2.1cpu高速缓存利用率 3.结语 1.随机链表的复制
一个长度为 n 的链表每个节点包含一个额外增加的随机指针 random 该指针可以指向链表中的任何节点或空节点。 1.2题目描述
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如如果原链表中有 X 和 Y 两个节点其中 X.random -- Y 。那么在复制链表中对应的两个节点 x 和 y 同样有 x.random -- y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示
val一个表示 Node.val 的整数。random_index随机指针指向的节点索引范围从 0 到 n-1如果不指向任何节点则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。
1.3题目分析 首先链表的拷贝如果是普通链表的话使用遍历尾插即可。 深度拷贝就是要链表结构也一样 但是由于随机指针的存在。我们没办法知道或者就是说我们拷贝的节点的随机指针该指向那个位置。那么就有一种简单粗暴的方法 遍历链表然后匹配随机指针。 那么巧妙的一种办法就是将复制的节点插到被复制节点的后面这种方法巧妙。时间复杂度为O(N).空间复杂度也为O(1). while(cur)//循环申请插入{//每次都申请节点struct Node* copy ( struct Node*)malloc(sizeof( struct Node));//尾插cur-val copy-val;cur -next copy;copy-next next;cur next;//往后走一步next cur-next;} 那么对于随机指针的连接 我们发现我们原链表的节点的随机指针指向的节点的next刚好就是我们复制链表节点的随机指针要指向的节点所以 //还要使用cur遍历cur head;struct Node* copy cue-next;while(cur){if(cur-random NULL){copy-random NULL;}else{copy-random cur-random-next;}cur copy-next;copy cur-next;} 然后我们将复制的节点从原链表取下来尾插成新的链表复原原链表就OK了 1.4解题 struct Node* copyRandomList(struct Node* head) {//1.首先先将复制的节点尾插到各个节点的后面assert(head);//断言不能传入一个空链表struct Node* cur head;struct Node* next cur-next;while(cur)//循环申请插入{//每次都申请节点struct Node* copy ( struct Node*)malloc(sizeof( struct Node));//尾插cur-val copy-val;cur -next copy;copy-next next;cur next;//往后走一步next cur-next;}//还要使用cur遍历cur head;struct Node* copy cur-next;while(cur){if(cur-random NULL){copy-random NULL;}else{copy-random cur-random-next;}cur copy-next;copy cur-next;}cur head;struct Node* copyhead NULL;//新链表的头结点struct Node* copytail NULL;//定义一个尾结点方便尾插//还是遍历解除复原while(cur){copy cur-next;next copy-next;//将cope结点开始尾插if(copytail NULL)//此时新链表一个元素都没有{copyhead copytail copy;}else{copytail-next copy;copytail copytail-next;}cur -next next;cur next;}return copyhead;}
2.顺序表和链表对比 不同点 顺序表 链表 存储空间上 物理上一定连续 逻辑上连续但物理上不一定 连续 随机访问 支持O(1) 不支持O(N) 任意位置插入或者删除元素可能需要搬移元素,效率低 O(N) 只需修改指针指向 插入 动态顺序表空间不够时需要 扩容 没有容量的概念 应用场景 元素高效存储频繁访问 任意位置插入和删除频繁 缓存利用率 高 低 2.1cpu高速缓存利用率
硬件上的存储分层如下图 3.结语 链表和顺序表的知识到这里基本就告一段落那么大家可以从知识到解题详细回顾一下。 可以结合图解多看一下代码结合理解。以上就是本期的所有内容知识含量蛮多大家可以配合解释和原码运行理解。创作不易大家如果觉得还可以的话欢迎大家三连有问题的地方欢迎大家指正一起交流学习一起成长我是Nicn正在c方向前行的奋斗者数据结构内容持续更新中感谢大家的关注与喜欢。
