当前位置:网站首页>Daily practice of LeetCode - 138. Copy a linked list with random pointers
Daily practice of LeetCode - 138. Copy a linked list with random pointers
2022-07-31 03:20:00 【airliner flying to the stars】
前言
Wassup guys!我是Edison
今天是 LeetCode 上的 leetcode 138. 复制带随机指针的链表
Let’s get it!
1. 题目描述
给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点.
构造这个链表的 深拷贝. 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值.
新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态.
复制链表中的指针都不应指向原链表中的节点 .
示例 1:
示例 2:
2. 思路分析
说实话,I saw this question for the first time,Didn't understand what it meant,The brain is dumbfounded
题目要求我们复制一个长度为 n 的链表,该链表除了每个节点有一个指针指向下一个节点外,还有一个 额外的指针 指向链表中的任意节点或者 null,如下图所示
如何去复制一个带随机指针的链表?
首先我们可以忽略 random 指针,然后对原链表的每个节点进行复制,并追加到原节点的后面,然后再去复制 random 指针.
最后我们把 原链表 和 复制链表 拆分出来,并将原链表复原.
图示过程如下:
1、在每个节点的后面加上它的复制,并将原链表和复制链表连在一起(如图所示).
什么意思呢?
也就是将 拷贝节点 连接在 原节点 后面
2、 从前往后 Traverse each original linked list node,对于有 random 指针的节点 p,我们让它的 p->next->random = p->random->next
,也就是说,这样我们就完成了对原链表 random 指针的复刻(如图所示).
什么意思呢?
拷贝节点的 random 在原节点 random 的后面.
p->next
It points to the copy node,p is our original node.
现在要将 原节点 的 random 拷贝到 拷贝节点 的 random 里面;
所以就是p->next->random = p->random->next
.
3、最后我们把 原链表 和 复制链表 拆分出来,并将原链表复原.
也就是说:
把 拷贝节点 拆分下来,linked together to make up 复制链表
3. 实现过程
The biggest difficulty is this 复制随机指针,比如下图中
节点 1 The random pointer points to the node 3
节点 3 The random pointer points to the node 2
节点 2 的随机指针指向 NULL;
We can solve this problem in three steps
拷贝
根据遍历到的原节点创建对应的新节点,每个新创建的节点是在原节点后面;
比如下图中原节点 1 不再指向原原节点 2,而是指向新节点 1
复制
这一步是最关键的一步,用来设置新链表的随机指针
上图中,我们可以观察到这么一个规律
原节点 1 的随机指针指向原节点 3,新节点 1 的随机指针指向的是原节点 3 的 next
原节点 3 的随机指针指向原节点 2,新节点 3 的随机指针指向的是原节点 2 的 next
也就是,原节点 i
的随机指针(如果有的话),指向的是原节点 j
那么新节点 i
的随机指针,指向的是原节点 j
的 next
split and reconnect
只要将两个链表分离开,再返回新链表就可以了
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; //Treat it as the original nodeval拷贝到copy节点
copy->next = cur->next; //put the original nodenext拷贝到copy节点的next
cur->next = copy; //Then let the original nodenext指向copy节点,Describes the current node andcopy节点连接起来了
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; // 我的randomequal to yoursrandom的next
}
cur = cur->next->next; //Why take two steps?因为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; // Reconnect the original linked list
if (copyTail == NULL) {
// 最开始copyTail是为空的
copyHead = copyTail = copy; // 直接把copy给它们
}
else {
copyTail->next = copy; //At this point, tail insertion is performed
copyTail = copyTail->next;
}
// 原链表的cur节点已经用完了, 让curPoints to the second node of the original linked list
cur = next;
}
//返回 复制链表 的头节点
return copyHead;
}
提交结果
边栏推荐
- The distance value between two arrays of LeetCode simple questions
- A brief introduction to the CheckBox component of the basic components of Flutter
- 什么是系统?
- Detailed explanation of TCP (1)
- 3.5 】 【 Cocos Creator slow operating system to stop all animations
- What is a distributed lock?Three ways of implementing distributed lock
- 【动态规划】连续子数组的最大和
- els block to the left to move the conditional judgment
- 选好冒烟测试用例,为进入QA的制品包把好第一道关
- TCP和UDP详解
猜你喜欢
随机推荐
STM32 problem collection
LeetCode simple problem to find the subsequence of length K with the largest sum
Mysql 45讲学习笔记(二十三)MYSQL怎么保证数据不丢
Getting Started with CefSharp - winform
LeetCode简单题之找到和最大的长度为 K 的子序列
LocalDate加减操作及比较大小
A brief introduction to the CheckboxListTile component of the basic components of Flutter
Mysql 45 study notes (twenty-four) MYSQL master-slave consistency
Mysql 45 study notes (twenty-five) MYSQL guarantees high availability
观察者模式
Problems that need to be solved in distributed system architecture
Is interprofessional examination difficult?Low success rate of "going ashore"?Please accept this practical guide!
自己的一些思考
[C language] Three-pointed chess (classic solution + list diagram)
【C语言】预处理操作
浅识Flutter 基本组件之showDatePicker方法
Why SocialFi achievement Web3 decentralized social in the future
The distance value between two arrays of LeetCode simple questions
MultipartFile文件上传
False positives and false negatives in testing are equally worthy of repeated corrections