当前位置:网站首页>LeetCode每日一练 —— 138. 复制带随机指针的链表
LeetCode每日一练 —— 138. 复制带随机指针的链表
2022-07-31 03:11:00 【飞向星的客机】
前言
Wassup guys!我是Edison
今天是 LeetCode 上的 leetcode 138. 复制带随机指针的链表
Let’s get it!
1. 题目描述
给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。
新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。
复制链表中的指针都不应指向原链表中的节点 。
示例 1:
示例 2:
2. 思路分析
说实话,我第一次看到这个题,都没有读懂要表达的是什么意思,大脑都是懵的
题目要求我们复制一个长度为 n 的链表,该链表除了每个节点有一个指针指向下一个节点外,还有一个 额外的指针 指向链表中的任意节点或者 null,如下图所示
如何去复制一个带随机指针的链表?
首先我们可以忽略 random 指针,然后对原链表的每个节点进行复制,并追加到原节点的后面,然后再去复制 random 指针。
最后我们把 原链表 和 复制链表 拆分出来,并将原链表复原。
图示过程如下:
1、在每个节点的后面加上它的复制,并将原链表和复制链表连在一起(如图所示)。
什么意思呢?
也就是将 拷贝节点 连接在 原节点 后面
2、 从前往后 遍历每一个原链表节点,对于有 random 指针的节点 p,我们让它的 p->next->random = p->random->next
,也就是说,这样我们就完成了对原链表 random 指针的复刻(如图所示)。
什么意思呢?
拷贝节点的 random 在原节点 random 的后面。
p->next
指向的就是拷贝节点,p 是我们的原节点。
现在要将 原节点 的 random 拷贝到 拷贝节点 的 random 里面;
所以就是p->next->random = p->random->next
。
3、最后我们把 原链表 和 复制链表 拆分出来,并将原链表复原。
也就是说:
把 拷贝节点 拆分下来,链接到一起组成 复制链表
3. 实现过程
这题的最大难点就在于 复制随机指针,比如下图中
节点 1 的随机指针指向节点 3
节点 3 的随机指针指向节点 2
节点 2 的随机指针指向 NULL;
我们可以用三步走来搞定这个问题
拷贝
根据遍历到的原节点创建对应的新节点,每个新创建的节点是在原节点后面;
比如下图中原节点 1 不再指向原原节点 2,而是指向新节点 1
复制
这一步是最关键的一步,用来设置新链表的随机指针
上图中,我们可以观察到这么一个规律
原节点 1 的随机指针指向原节点 3,新节点 1 的随机指针指向的是原节点 3 的 next
原节点 3 的随机指针指向原节点 2,新节点 3 的随机指针指向的是原节点 2 的 next
也就是,原节点 i
的随机指针(如果有的话),指向的是原节点 j
那么新节点 i
的随机指针,指向的是原节点 j
的 next
拆分再连接
只要将两个链表分离开,再返回新链表就可以了
4. 代码实现
接口代码
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; //把当原节点的val拷贝到copy节点
copy->next = cur->next; //把原节点的next拷贝到copy节点的next
cur->next = copy; //然后再让原节点的next指向copy节点,说明当前节点与copy节点连接起来了
cur = cur->next->next; //开始迭代,cur->next是copy节点,copy->next->next是原链表的第二个节点
}
// 2.再次遍历,更新拷贝节点的random
cur = head; // 继续让cur指向原链表的头节点
while (cur) {
struct Node* copy = cur->next;
// ①如果原节点的random为空,那么copy节点的random也为空
if (cur->random == NULL) {
copy->random = NULL;
}
else {
// ②如果原节点的random的不为空
copy->random = cur->random->next; // 我的random就等于你的random的next
}
cur = cur->next->next; //为什么要跳两步呢?因为cur中间有个copy节点
}
// 3.把拷贝节点解下来,链接到一起
cur = head;
struct Node* copyHead = NULL, *copyTail = NULL;
while (cur) {
struct Node* copy = cur->next; // copy节点
struct Node* next = copy->next; // 原链表的 原节点 的 下一个节点
cur->next = next; // 把原链表再重新连接起来
if (copyTail == NULL) {
// 最开始copyTail是为空的
copyHead = copyTail = copy; // 直接把copy给它们
}
else {
copyTail->next = copy; //此时就进行尾插了
copyTail = copyTail->next;
}
// 原链表的cur节点已经用完了, 让cur指向原链表的第二个节点
cur = next;
}
//返回 复制链表 的头节点
return copyHead;
}
提交结果
边栏推荐
- 【Exception】The field file exceeds its maximum permitted size of 1048576 bytes.
- Crypto Firms Offer Offer To Theft Hackers: Keep A Little, Give The Rest
- The distance value between two arrays of LeetCode simple questions
- Recursive query single table - single table tree structure - (self-use)
- [Godot][GDScript] 二维洞穴地图随机生成
- 5. SAP ABAP OData 服务如何支持 $filter (过滤)操作
- 加密公司向盗窃的黑客提供报价:保留一点,把剩下的归还
- SQL 面试用题(重点)
- Map.Entry理解和应用
- els block to the right
猜你喜欢
CorelDRAW2022 streamlined Asia Pacific new features in detail
YOLOV5 study notes (2) - environment installation + operation + training
6. Display comments and replies
【C语言】预处理操作
【C语言】表达式求值的一般方法
7. List of private messages
Project (5) - Small target detection tph-yolov5
Use of QML
Ambiguous method call.both
Detailed explanation of TCP (3)
随机推荐
SQALE 是什么
Moxa NPort 设备缺陷可能使关键基础设施遭受破坏性攻击
【C语言】表达式求值的一般方法
The distance value between two arrays of LeetCode simple questions
els block to the right
Detailed explanation of TCP (3)
Thesis framework of the opening report
[C language] Preprocessing operation
【C语言】三子棋(经典解法+一览图)
How to build a private yum source
共模电感的仿真应用来了,满满的干货送给大家
Redis实现分布式锁
6、显示评论和回复
The use of font compression artifact font-spider
Redis implements distributed locks
Discourse Custom Header Links
Detailed explanation of TCP (1)
Day32 LeetCode
C primer plus学习笔记 —— 8、结构体
注解用法含义