当前位置:网站首页>[C题目]力扣138. 复制带随机指针的链表
[C题目]力扣138. 复制带随机指针的链表
2022-08-02 20:33:00 【GLC8866】
题目要求: 给你一个链表A,其中结点的next用于连接前后结点,random指向当前链表A任意结点位置或者是NULL,此时需要你再创建一个相同结构的链表B,链表B与链表A长度一样、对应位置结点的val值一样、每个结点的random指向当前链表的第几个结点也一样。
思路:在链表A的每一个结点cur后面插入一个新的结点copy,cur的random指向为cur->random,而copy的random指向为cur->random->next时就能拷贝出相同的结构。当cur->next指向NULL时为特殊情况,copy->random直接指向NULL即可。
struct Node* copyRandomList(struct Node* head)
{
//在旧链表中的每一个结点后插入新结点
struct Node* cur=head;
while(cur)
{
//创建新结点copy
struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
copy->val=cur->val;
//将新结点插入cur结点的后面
copy->next=cur->next;
cur->next=copy;
//换下一个cur,直到为NULL后不再插入新结点。
cur=copy->next;
}
//新结点复制前一个结点对应的random指向结构
//与cur相对应的结点为cur->next
cur=head;
while(cur)
{
struct Node* copy=cur->next;
//random为NULL不满足复制的规律
if(cur->random==NULL)
{
copy->random=NULL;
}
else
{
copy->random=cur->random->next;
}
//换下一个cur,直到为NULL不再对cur->next进行复制random结构。
cur=copy->next;
}
//拆解链表
cur=head;
//创建哨兵位头结点copyhead,并且初始时copyhead->next必须为NULL。
struct Node* copyhead=(struct Node*)malloc(sizeof(struct Node));
copyhead->next=NULL;
//尾结点初始时为copyhead。
struct Node* copytail=copyhead;
//将每一个cur->next拆解下来尾插到copytail后面,直到cur为止。
while(cur)
{
//用copy标记cur->next。
struct Node* copy=cur->next;
//将copy尾插到copytail后面。
copytail->next=copy;
//尾结点copytail更新。
copytail=copytail->next;
//下一个cur连接上前一个cur
cur->next=copy->next;
//对下一个cur进行判断
cur=cur->next;
}
return copyhead->next;
}
边栏推荐
- MSTP与STP
- 10 种最佳 IDE 软件 ,你更忠爱哪一个?
- Which thread pool does Async use?
- callback prototype __proto__
- Digital twins help visualize the construction of smart cities
- 如何成为一名正义黑客?你应该学习什么?
- Common tools and test methods for interface testing (Introduction)
- Wiring diagrams of switches, motors, circuit breakers, thermocouples, and meters
- The software testing process specification is what?Specific what to do?
- 拥抱Cmake小朋友 简单又实用,但是不灵活
猜你喜欢
随机推荐
浅议.NET遗留应用改造
什么是 IDE
基本语法(三)
PLC工作原理动画
.NET performance optimization - you should set initial size for collection types
Packages and packages, access modifiers
李沐动手学深度学习V2-BERT预训练和代码实现
解道6-编程技术3
解道8-编程技术5
How the sensor works
pytorch的tensor创建和操作记录
go——垃圾回收机制(GC)
汇编语言中b和bl关键字的区别
你所不知道的C#中的细节
【SLAM】DM-VIO(ros版)安装和论文解读
js how to get the browser zoom ratio
Flink Yarn Per Job - 启动AM
Xcode13.1运行工程报错fatal error: ‘IFlyMSC/IFly.h‘ file not found的问题
博客主页rrs代码
golang 源码分析:uber-go/ratelimit