行业知识
【数据结构和算法初阶(C语言)】复杂链表（随机指针，随机链表的复制）题目详解+链表顺序表结尾
���录
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++方向前行的奋斗者，数据结构内容持续更新中，感谢大家的关注与喜欢。
