朋友们、伙计们,我们又见面了,本期来给大家解读一下LeetCode中第138道单链表OJ题,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成!
数据结构与算法专栏:数据结构与算法
个 人 主 页 :stackY、
C 语 言 专 栏:C语言:从入门到精通
LeetCode--138.复制带随即指针的链表:https://leetcode.cn/problems/copy-list-with-random-pointer/description/
目录
1.题目介绍
2.实例演示
3.解题思路
::链接拷贝结点 ::
::找拷贝节点的random ::
:: 拆解拷贝链表 ::
1.题目介绍
给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
小编现在这里向大家袒露心扉一下:其实我刚刚看到这个单链表OJ题,看了半天连题目都没咋搞明白,好不容易看懂了题目介绍,可是又不知道该从何下手,然后求助各种大佬,才慢慢理解,然后整理思路,在这篇文章中将这道题分享给大家。
2.实例演示
3.解题思路
这道题应该算是单链表OJ题中比较复杂的一道题了,主要是比较难理解。题目的主要意思就是要拷贝出与原链表一模一样的一个链表。那么这道题拷贝链表都不是很复杂,比较难处理的就是这个随即指针random的指向,如果原链表的random指向空那这好说,拷贝链表的也指向空,但是如果原链表的random指向非空,那该如何去找这个random呢?在这里呢,很多老铁喜欢用random指向的值来比较,这种想法可以,但是架不住链表中有相同的值,那么就有许多老铁用它的random指向的地址来比较,这种方法是完全可行的,但是呢,这种暴力求解的方法往往都不是最优解,使用地址来进行比较的话它的时间复杂度是O(N^2),效率也是不太行。所以我们需要寻求更优解。
这道题的解题思路我分为了三个步骤:
1. 链接拷贝结点:
将拷贝结点插入到原结点的后面。
2. 找拷贝节点的random:
通过原链表来控制拷贝结点的随机指针random。
3. 拆解拷贝链表:
将拷贝结点拆下来,依次尾插组成新的链表,然后恢复原链表。
接下来我们一步一步来进行解题:
::链接拷贝结点 ::
我们可以将拷贝结点链接在原结点的后面,这种方法比较巧妙,有助于我们找随即指针random。
先创建拷贝节点,然后遍历原链表,然后保存头节点的下一个结点,改变指向,将拷贝节点插入到原结点的后面。
图示:
代码演示:
/**
* Definition for a Node.
* struct Node {
* int val;
* struct Node *next;
* struct Node *random;
* };
*/
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;
//保存头指针的下一个结点
struct Node* curNext = cur->next;
//链接
cur->next = copy;
copy->next = curNext;
cur = curNext;
}
//......
}
::找拷贝节点的random ::
当我们将拷贝结点链接在原结点的后面时,我们需要找拷贝结点的随机指针random,这里可以分为两种情况:
1. 如果原结点的random是空,那么直接将拷贝结点的random置为空即可。
2. 若不为空,那么就需要观察一下这个链表,拷贝结点的random指针指向的就是原结点的random指向的结点的next结点:
copy -> random = cur -> random -> next;
因为我们将拷贝结点链接在了原结点的后面,那么原结点的random指向的结点的next结点就是拷贝结点要找的random。我们依旧遍历整个链表,然后将拷贝节点的随机指针链接。
图示:
代码演示:
/**
* Definition for a Node.
* struct Node {
* int val;
* struct Node *next;
* struct Node *random;
* };
*/
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;
//保存头指针的下一个结点
struct Node* curNext = cur->next;
//链接
cur->next = copy;
copy->next = curNext;
cur = curNext;
}
//2.找拷贝节点的random
//重新返回头
cur = head;
while(cur)
{
//找拷贝结点
struct Node* copy = cur->next;
//找下一个结点
struct Node* next = copy->next;
//链接拷贝节点的随机指针random
if(cur->random == NULL)
{
copy->random = NULL;
}
else
{
copy->random = cur->random->next;
}
//遍历
cur = next;
}
//......
}
:: 拆解拷贝链表 ::
我们找到了拷贝链表之后呢,需要将这些拷贝的结点组成一个新的链表,这就需要将这些拷贝结点依次进行尾插,然后再将原链表恢复。这就比较简单了:
图示:
完整代码演示:
/**
* Definition for a Node.
* struct Node {
* int val;
* struct Node *next;
* struct Node *random;
* };
*/
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;
//保存头指针的下一个结点
struct Node* curNext = cur->next;
//链接
cur->next = copy;
copy->next = curNext;
cur = curNext;
}
//2.找拷贝节点的random
//重新返回头
cur = head;
while(cur)
{
//找拷贝结点
struct Node* copy = cur->next;
//找下一个结点
struct Node* next = copy->next;
//链接拷贝节点的随机指针random
if(cur->random == NULL)
{
copy->random = NULL;
}
else
{
copy->random = cur->random->next;
}
//遍历
cur = next;
}
//3.拆解拷贝结点,恢复原链表
//重新返回头
cur = head;
//创建新的链表
struct Node* copyHead = NULL;
struct Node* copyTail = NULL;
while(cur)
{
//找拷贝结点
struct Node* copy = cur->next;
//找下一个结点
struct Node* next = copy->next;
//尾插拷贝节点构成新的链表
if(copyTail == NULL)
{
copyHead = copyTail = copy;
}
else
{
copyTail->next = copy;
copyTail = copyTail->next;
}
//恢复原链表
cur->next = next;
cur = next;
}
return copyHead;
}
朋友们、伙计们,美好的时光总是短暂的,我们本期的的分享就到此结束,最后看完别忘了留下你们弥足珍贵的三连喔,感谢大家的支持!
发表评论