力扣LeetCode138. 复制带随机指针的链表 两种解法（C语言实现）

目录

题目链接

题目分析

 题目定位：

解题思路

解题思路1（粗暴但是复杂度高）

 解题思路2（巧妙并且复杂度低）

题目链接

138. 复制带随机指针的链表icon-default.png?t=N7T8https://leetcode-cn.com/problems/copy-list-with-random-pointer/

题目分析

 题目定位：

本题属于链表中较为综合的题目，考验做题者的思想以及用代码实现的能力，能够真正理解并做出此题需要对链表有相对熟练的掌握度。

话不多说，先来分析题目：

题目是想让我们构造一个链表的拷贝，也就是开辟一块一模一样的链表，但是本题中的链表，又和普通的单链表不一样，如图：

我们发现，链表中每一个节点中的结构体成员除了val和next之外，还有一个random，而random是指向链表中的任意一个节点，甚至可以是NULL。

因此要拷贝这个链表的难度就在于，如何使拷贝的链表中每一个节点的random指向其对应的节点呢？

解题思路

解题思路1（粗暴但是复杂度高）

第1步.先忽略原链表的random指针，对其进行复制，如图：

(1)定义两个struct Node*类型的指针copyhead和copytail来储存复制链表的头和尾，并初始化为NULL；并且定义一个struct Node*类型的指针cur指向head

(2)若原链表不为空，则此时cur指向第一个节点。用malloc开辟一块空间作为复制的第一个节点，并定义一个copy指针来保存，并将copy->val改为cur->val，并让copyhead和copytail指向copy节点

(3)让cur移向下一个节点。用malloc开辟一块空间作为复制的第二个节点，并让copy指向它，并将copy->val改为cur->val，先让copytail->next指向copy来连接两个节点，再让copytail指向copy节点(更新尾节点)。

像这样一直循环下去直到cur指向NULL，循环结束，最后再让copytail->next = NULL，此时便完成了第一步的复制操作

此时我们便可以根据图解来写代码

struct Node* copyRandomList(struct Node* head) {
	//1.忽略random复制链表
    struct Node* cur = head;
    struct Node* copyhead = NULL;
    struct Node* copytail = NULL;
    while(cur)
    {
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node))；
        copy->val = cur->val;
        if(copyhead == NULL)
        {
            copyhead = copy;
            copytail = copy;
        }
        else
        {
            //先连接
            copytail->next = copy;
            //再指向copy
            copytail = copy;
        }
        cur = cur->next;
    }
    copytail->next = NULL;
}

第2步.处理拷贝链表的random指针

(1)查找原链表中的random指向的节点到底是第几个节点，并定义一个变量pos来记录下来

①如果原链表random指向NULL，则不需要找pos

②如果原链表的random指向链表中的节点，每次循环开始可以初始化一个新的指针newcur=head，再对newcur进行迭代，每当newcur向后走一次，pos加一，直到newcur == cur->random的时候，循环结束，举一个例子：

 (2)用一个循环来使拷贝链表中random指向其对应的节点

①如果原链表的random指向NULL，那么便很简单：拷贝的random直接置为NULL；

②如果原链表的random指向链表中的节点，每次循环开始可以初始化一个新的指针newcopy=copyhead,那么拷贝的random则可以通过一个循环来找到pos所对应的第几个节点，接着上面的例子：

根据图解我们可以写出代码：

struct Node* copyRandomList(struct Node* head) {
	//1.忽略random复制链表
    struct Node* cur = head;
    struct Node* copyhead = NULL;
    struct Node* copytail = NULL;
    while (cur)
    {
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
            copy->val = cur->val;
        if (copyhead == NULL)
        {
            copyhead = copy;
            copytail = copy;
        }
        else
        {
            //先连接
            copytail->next = copy;
            //再指向copy
            copytail = copy;
        }
        cur = cur->next;
        copytail->next = NULL;
    }
    //2.处理拷贝链表的random指针
    cur = head;
    struct Node* copy = copyhead;
    while (cur)
    {
        int pos = 0;
        if (cur->random == NULL)
        {
            copy->random = NULL;
        }
        //找到cur的random指向对应的第几个节点
        else
        {
            //让newcur和newcopy重新指向第一个节点
            struct Node* newcur = head;
            struct Node* newcopy = copyhead;
            while (newcur != cur->random)
            {
                newcur = newcur->next;
                pos++;
            }
            //使copy的random指向对应的第pos个节点
            while (pos--)
            {
                newcopy = newcopy->next;
            }
            copy->random = newcopy;
        }
        //cur和copy向后走
        cur = cur->next;
        copy = copy->next;
    }
    return copyhead;
}

 题解一总结：优点是这种思路比较容易想到并且理解；缺点是由于找到原链表找到random指向的节点的pos的过程，每个节点的复杂度为O(n)，又有n个节点，因此这种解法的时间复杂度为O(n²)，并不是一个优秀的解法，接下来将为大家讲另一种优秀的解法。

 解题思路2（巧妙并且复杂度低）

第1步 把拷贝节点连接再原节点的后面

用这种方式处理是为了方便找到拷贝链表的random应该指向第几个节点，random指向的这个节点的下一个节点就是拷贝链表要找的random节点

根据图解我们可以写出代码：

//1.链接链表
    struct Node* cur = head;
    while(cur)
    {
        //提前储存原链表下一个节点的地址
        struct Node* next = cur->next;
        //为原链表的拷贝开辟空间
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;
        //链接原链表和拷贝节点
        cur->next = copy;
        copy->next = next;
        //迭代往下走
        cur = next;
    }

 第2步 拷贝原链表的random节点

 (1)若原链表的节点的random指向NULL，拷贝节点的random也指向NULL

(2)若原链表的节点random指向原链表的其中一个节点，那么random指向的这个节点的下一个节点就是拷贝链表要找的random，以原链表二个节点为例：

(3)实现后题解如下

根据图解我们可以写出代码：

//2.拷贝原链表的random节点
    cur = head;
    while(cur)
    {
        struct Node* copy = cur->next;
        if(cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }
        cur = copy->next;
    }

第3步 将拷贝节点与原链表分开

(1)用cur和copy指针来分别使原链表和拷贝链表的节点向后迭代，由于copy随着cur向后迭代，一直跟在cur的后面

因此循环外初始化cur = head，循环内初始化copy = cur->next;

 (2)为原链表定义一个next来连接链表；为拷贝链表定义一个copyhead和copytail来返回和连接链表，当原链表第一个节点不为空，才能保证copy的第一个节点不为空，因此copyhead和copytail先置空

循环外初始化copytail = copyhead = NULL，循环内初始化next = copy->next, 

(3)当cur指向第一个节点时，进入循环，此时copyhead和copytail为空，使其指向拷贝链表的第一个节点，再使cur->next = next，将cur和next连接起来，并使cur=next往后走，

 若cur不为空，再之后就是让copy=cur->next，next = copy->next

  捋清楚结构就可以写出循环体框架：

    cur = head;
    struct Node* copyhead = NULL;
    struct Node* copytail = NULL;
    while(cur)
    {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;
        if(copyhead == NULL)
        {
            copyhead = copytail = copy;
        }
        cur->next = next;
        cur = next;
    }

(4)当cur指向第二个节点时，copyhead和copytail此时不为空，copy也指向拷贝的第二个节点，因此用copytail->next = copy连接两节点，再使copytail = copy使其向后迭代

捋清关系我们便可以补全循环体

//3.将拷贝节点与原链表分开
    cur = head;
    struct Node* copyhead = NULL;
    struct Node* copytail = NULL;
    while(cur)
    {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;
        if(copyhead == NULL)
        {
            copyhead = copytail = copy;
        }
        else
        {
            copytail->next = copy;
            copytail = copy;
        }
        cur->next = next;
        cur = next;
    }

完整代码： 

struct Node* copyRandomList(struct Node* head) {
	//1.链接链表
    struct Node* cur = head;
    while(cur)
    {
        //提前储存原链表下一个节点的地址
        struct Node* next = cur->next;
        //为原链表的拷贝开辟空间
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;
        //链接原链表和拷贝节点
        cur->next = copy;
        copy->next = next;
        //迭代往下走
        cur = next;
    }
    //2.拷贝原链表的random节点
    cur = head;
    while(cur)
    {
        struct Node* copy = cur->next;
        if(cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }
        cur = copy->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(copyhead == NULL)
        {
            copyhead = copytail = copy;
        }
        else
        {
            copytail->next = copy;
            copytail = copy;
        }
        cur->next = next;
        cur = next;
    }
    return copyhead;
}

 题解二总结：由于第二种解题思路用巧妙的连接方式，使拷贝链表的random不需要通过对原链表的每一个节点遍历也能找到，大大降低了时间复杂度，这种解法的时间复杂度为O(n)。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/541375.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

双写一致性问题

双写一致性问题

双写一致性问题：同一份数据，需要写数据库、写缓存。数据库中的数据和缓存中的数据要一致 解决办法：延迟双删 当我们要进行更新操作时，先删除缓存，再更新数据库，延迟几百ms再删除一次redis的缓存数据。 示…
阅读更多...
2023年蓝桥杯——日期统计

2023年蓝桥杯——日期统计

目录 题目链接：1.日期统计 - 蓝桥云课 (lanqiao.cn) 题目描述 思路 代码思路 定义数据结构： 处理每一个月： 检查日期序列在num100中是否存在： 计数匹配的日期数： 输出结果： 代码实现 总结 题目链…
阅读更多...
【Python习题】某景区门票的优惠措施为:购买5张以内门票不打折，5到20张打九折，20张以上打八折。编写程序，根据购买的门票数量，输出总票价。

【Python习题】某景区门票的优惠措施为:购买5张以内门票不打折，5到20张打九折，20张以上打八折。编写程序，根据购买的门票数量，输出总票价。

题干 某景区门票的优惠措施为:购买5张以内门票不打折，5到20张打九折，20张以上打八折。编写程序，根据购买的门票数量，输出总票价。 代码
阅读更多...
介绍几个好用的电商（淘宝京东1688）API接口，可测试

介绍几个好用的电商（淘宝京东1688）API接口，可测试

以下是几个好用的电商（淘宝、京东、1688）API接口，这些接口都可以进行测试以确保其稳定性和可用性： taobao.item_get-获取淘宝商品数据接口返回值说明 1.请求方式：HTTP POST GET （复制薇：Anzex…
阅读更多...
2024.4.13 Python 爬虫复习day01

2024.4.13 Python 爬虫复习day01

目录 day01_HTTP协议HTML页面web服务器 各类名词解释 URL统一资源定位符 HTTP协议 HTML页面 知识点: 第一个页面 标题标签和图片标签 注册页面 登录页面 WEB服务器 安装fastapi和uvicorn 原始命令方式 镜像源命令方式 工具方式 快速搭建web服务器 知识点: 示例…
阅读更多...
CH254X 8051芯片手册介绍

CH254X 8051芯片手册介绍

1 8051CPU 8051是一种8位元的单芯片微控制器，属于MCS-51单芯片的一种，由英特尔(Intel)公司于1981年制造。Intel公司将MCS51的核心技术授权给了很多其它公司，所以有很多公司在做以8051为核心的单片机，如Atmel、飞利浦、深联华等公…
阅读更多...
ARMv8-A架构下的外部debug模型之外部调试事件（external debug events）概述

ARMv8-A架构下的外部debug模型之外部调试事件（external debug events）概述

外部调试器与处理器之间的握手与external debug events 一，External Debug的使能二，外部调试器和CPU之间的握手三，外部调试事件 External debug events1. External debug request event2. Halt instruction debug event3. Halting step debug…
阅读更多...
是的，本科毕业八年，我考研了

是的，本科毕业八年，我考研了

今天，是一篇纯分享文。 是的，本科毕业八年，我考研了。 停更10个月，历时296天，我考研上岸了。 小伙伴们，好久不见。 一 发今年第一篇文章的时候刚处理完后续事宜，就简单说了句，后台…
阅读更多...
Vue3 ts环境下的PropType

Vue3 ts环境下的PropType

简介 在Typscript中，我们可以使用PropType进行类型的推断与验证。在日常的开发中我们常常会遇到下面这样的场景： 我们通过request请求从服务端获取了一条数据，数据是个Array的格式，Array中的每个元素又是一个对象，像下…
阅读更多...
【神经网络与深度学习】循环神经网络基础

【神经网络与深度学习】循环神经网络基础

tokenization tokenization：分词 每一个词语都是token 分词方法：转为单个词、转为多个词语 N-gram表示法 准备词语特征的方法 （把连续的N个词作为特征） 如 ”我爱你“——>[我，爱，你] 2-gram——[[我…
阅读更多...
java项目之校园兼职系统（ssm框架+mysql数据库+文档）

java项目之校园兼职系统（ssm框架+mysql数据库+文档）

项目简介 校园兼职系统的主要使用者分为：管理员：首页、个人中心、专业管理、商家管理、热门兼职管理、学生管理、兼职接单管理、学生咨询管理、兼职任务管理、完成评价管理、管理员管理、系统管理等模块信息的查看及相应操作；学生&#xff1…
阅读更多...
在vue中配置样式 max-width：100px时，发现和width:100px一样没有对应的递增到最大宽度的效果？怎么回事？怎么解决？

在vue中配置样式 max-width：100px时，发现和width:100px一样没有对应的递增到最大宽度的效果？怎么回事？怎么解决？

原因： 可能时vue的样式大部分和display相关，有很多的联系，导致不生效 解决： 对设置max-width样式的元素设置display:inline-block;属性，即可生效，实现随着子元素的扩展而扩展并增加固定到最大的宽度
阅读更多...
使用 ASE 拼接分子

使用 ASE 拼接分子

在部分应用场景下，我们需要对两个分子片段进行拼接，例如锂电电解液数据库 LiBE 然而，当前并没有合适的拼接方法。下面是一些已有方法的调研结果： 在 LiBE 论文的附录里，作者使用 pymatgen 进行分子拼接。 其思路是&…
阅读更多...
分享2024高校专业建设思路及建设效果

分享2024高校专业建设思路及建设效果

广东泰迪智能科技股份有限公司成立于2013年，是一家专业从事大数据、人工智能等数据智能技术研发、咨询和培训的高科技企业，公司基于十余年的数据智能产业实践经验，构建“产、岗、课、赛、证、文”融通的特色应用型人才培养模式，助…
阅读更多...
MQ:延迟队列

MQ:延迟队列

6.1场景： 1.定时发布文章 2.秒杀之后，给30分钟时间进行支付，如果30分钟后，没有支付，订单取消。 3.预约餐厅，提前半个小时发短信通知用户。 A -> 13:00 17:00 16:30 延迟时间： 7*30 * 60 *…
阅读更多...
微信营销快捷回复和微信多开-微信UI自动化(.Net)

微信营销快捷回复和微信多开-微信UI自动化(.Net)

整理 | 小耕家的喵大仙 出品 | CSDN（ID：lichao19897314） Q Q | 978124155 关于项目背景和本软件的介绍 因为本人前期基于微信自动化这块编写了一些文章，所以最近想着将文章内容点合并后开发一款真正能帮助别人的软件&#xff0…
阅读更多...
AI赋能档案开放审核：实战

AI赋能档案开放审核：实战

关注我们 - 数字罗塞塔计划 - 为进一步推进档案开放审核工作提质增效，结合近几年的业务探索、研究及项目实践，形成了一套较为成熟、高效的AI辅助档案开放审核解决方案，即以“AI人工”的人机协同模式引领档案开放审机制创新，在档…
阅读更多...
07.QT信号和槽-2

07.QT信号和槽-2

一、自定义信号和槽 在Qt中，允许⾃定义信号的发送⽅以及接收⽅，即可以⾃定义信号函数和槽函数。但是对于⾃定义的信号函数和槽函数有⼀定的书写规范。 1.基本语法 1.1 自定义信号 （1）⾃定义信号函数必须写到"signals"…
阅读更多...
Windows不常见问题集

Windows不常见问题集

● 解决CACLS 禁止修改计算机名 管理员权限运行cmd：cacls %SystemRoot%\System32\netid.dll /grant administrators:f ● Excel 2010 AltTab組合鍵設置 HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Explorer，在該路徑建32字元DWO…
阅读更多...
YOLOv8使用设备摄像头实时监测

YOLOv8使用设备摄像头实时监测

代码如下： from ultralytics import YOLO import cv2 from cv2 import getTickCount, getTickFrequency yoloYOLO(./yolov8n.pt)#摄像头实时检测cap cv2.VideoCapture(0) while cap.isOpened():loop_start getTickCount() #记录循环开始的时间，用于计…
阅读更多...
最新文章

Copyright @ 2022~2023