力扣LeetCode138. 复制带随机指针的链表 两种解法(C语言实现)
目录
题目链接
题目分析
题目定位:
解题思路
解题思路1(粗暴但是复杂度高)
解题思路2(巧妙并且复杂度低)
题目链接
138. 复制带随机指针的链表https://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;//再指向copycopytail = 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;//再指向copycopytail = 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)。
相关文章:
力扣LeetCode138. 复制带随机指针的链表 两种解法(C语言实现)
目录 题目链接 题目分析 题目定位: 解题思路 解题思路1(粗暴但是复杂度高) 解题思路2(巧妙并且复杂度低) 题目链接 138. 复制带随机指针的链表https://leetcode-cn.com/problems/copy-list-with-random-pointer/ …...
强大的压缩和解压缩工具 Keka for Mac
Keka for Mac是一款功能强大的压缩和解压缩工具,专为Mac用户设计。它支持多种压缩格式,包括7z、Zip、Tar、Gzip和Bzip2等,无论是发送电子邮件、备份文件还是节省磁盘空间,Keka都能轻松满足用户需求。 这款软件的操作简单直观&…...
论文速读:Do Generated Data Always Help Contrastive Learning?
在对比学习领域,最近很多研究利用高质量生成模型来提升对比学习 给定一个未标记的数据集,在其上训练一个生成模型来生成大量的合成样本,然后在真实数据和生成数据的组合上执行对比学习这种使用生成数据的最简单方式被称为“数据膨胀”这与数据…...
华为欧拉系统(openEuler-22.03)安装深信服EasyConnect软件(图文详解)
欧拉镜像下载安装 iso镜像官网下载地址 选择最小化安装,标准模式 换华为镜像源 更换华为镜像站,加速下载: sed -i "s#http://repo.openeuler.org#https://mirrors.huaweicloud.com/openeuler#g" /etc/yum.repos.d/openEuler.r…...
git commit --amend用法
一、git commit --amend 修改提交信息:您可以使用 git commit --amend 命令来修改最新提交的提交信息。执行该命令后,Git 将会打开文本编辑器(通常是的默认文本编辑器),以便编辑提交信息。完成编辑后保存并关闭编辑器…...
分布式系统:缓存与数据库一致性问题
前言 缓存设计是应用系统设计中重要的一环,是通过空间换取时间的一种策略,达到高性能访问数据的目的;但是缓存的数据并不是时刻存在内存中,当数据发生变化时,如何与数据库中的数据保持一致,以满足业务系统…...
JavaEE企业开发新技术5
目录 2.18 综合应用-1 2.19 综合应用-2 2.20 综合应用-3 2.21 综合应用-4 2.22 综合应用-5 Synchronized : 2.18 综合应用-1 反射的高级应用 DAO开发中,实体类对应DAO的实现类中有很多方法的代码具有高度相似性,为了提供代码的复用性,降低…...
mysql dump导出导入数据
前言 mysqldump是MySQL数据库中一个非常有用的命令行工具,用于备份和还原数据库。它可以将整个数据库或者特定的表导出为一个SQL文件,以便在需要时进行恢复或迁移。 使用mysqldump可以执行以下操作: 备份数据库:可以使用mysqld…...
刷题记录3
# 10 字符个数统计 描述 编写一个函数,计算字符串中含有的不同字符的个数。字符在 ASCII 码范围内( 0~127 ,包括 0 和 127 ),换行表示结束符,不算在字符里。不在范围内的不作统计。多个相同的字符只计算一次 例如,对…...
Decorator 装饰
意图 动态的给一个对象添加一些额外的职责。就增加功能而言,Decorator模式比生成子类更加灵活 结构 其中: Component定义一个对象接口,可以给这些对象动态的添加职责。ConcreteComponent定义一个对象,可以给这个对象添加一些职…...
SpringMVC:搭建第一个web项目并配置视图解析器
👉需求:用spring mvc框架搭建web项目,通过配置视图解析器达到jsp页面不得直接访问,实现基本的输出“hello world”功能。👩💻👩💻👩💻 1 创建web项目 1…...
一文了解HTTPS的加密原理
HTTPS是一种安全的网络通信协议,用于在互联网上提供端到端的加密通信,确保数据在客户端(如Web浏览器)与服务器之间传输时的机密性、完整性和身份验证。HTTPS的加密原理主要基于SSL/TLS协议,以下详细阐述其工作过程&…...
Ubuntu系统空间整理
查看文件大小命令 查看文件以及文件夹大小 ls -hl #查看文件大小,-h 表示Human-Readable ll -h #查看文件夹的大小 #du命令查看文件或文件夹的磁盘使用空间,–max-depth 用于指定深入目录的层数。#查看当前目录已经使用总大小及当前目录下一级文件或…...
PHP Storm 2024.1使用
本文讲的是phpstorm 2024.1最新版本激活使用教程,本教程适用于windows操作系统。 1.先去idea官网下载phpstorm包,我这里以2023.2最新版本为例 官网地址:https://www.jetbrains.com/zh-cn/phpstorm/ 2.下载下来后安装,点下一步 …...
王东岳-知鱼之乐【边读边记】1
2024-04-15 21:00 终于打算开始读这本书了,作者王东岳,第一次听到这个名字,是因为传说王东岳是李善友的师父,我是先从混沌学院知道的李善友,因为李善友还是有东西的,所以我对王东岳起步也是非常尊敬的。所以…...
迁移docker部署的GitLab
目录 1. 背景2. 参考3. 环境4. 过程4.1 查看原docker启动命令4.2 打包挂载目录传至新宿主机并创建对应目录4.3 保存镜像并传至新宿主机下4.4 新宿主机启动GitLab容器 5 故障5.1 容器不断重启5.2 权限拒绝5.3 容器内错误日志 6 重启容器服务正常7 总结 1. 背景 最近接到一个任务…...
今年消费新潮流:零元购商业模式
今天给大家推荐一种极具创新的电子商务模式:零元购商业模式 这个模式支持消费者以零成本或极低成本购买商品。这种模式主要通过返现、积分、优惠券等方式来减少支付金额,使消费者实现“零成本”购物的目标。 人民网在去年发表了一篇文章。 总结了一下&a…...
Go导入私有仓库
使用go.mod依赖第三方库时,有以下要求: 代码仓库托管于VCS(版本控制系统);代码仓库是公开的;仓库地址使用域名访问;仓库域名支持HTTPS访问。 对于自己或者公司内部搭建的私有git,这些条件是比较难同时满足…...
GIS GeoJSON数据获取
1、工具地址 DataV.GeoAtlas地理小工具系列 2、界面预览...
书生·浦语大模型实战营 | 第3次学习笔记
前言 书生浦语大模型应用实战营 第二期正在开营,欢迎大家来学习。(参与链接:https://mp.weixin.qq.com/s/YYSr3re6IduLJCAh-jgZqg 第三堂课的视频链接:https://www.bilibili.com/video/BV1QA4m1F7t4/ 本次笔记是学习完第三堂课…...
easyExcel - 按模板导出
目录 前言一、情景介绍二、文档介绍2.1 读取模板2.2 填充模板 三、代码示例3.1 案例一:工资表3.2 案例二:报价单 四、我所遇到的问题 前言 Java-easyExcel入门教程:https://blog.csdn.net/xhmico/article/details/134714025 之前有介绍过如…...
使用 Tranformer 进行概率时间序列预测实战
使用 Transformers 进行概率时间序列预测实战 通常,经典方法针对数据集中的每个时间序列单独拟合。然而,当处理大量时间序列时,在所有可用时间序列上训练一个“全局”模型是有益的,这使模型能够从许多不同的来源学习潜在的表示。…...
LLM大语言模型助力DataEase小助手,新增气泡地图,DataEase开源数据可视化分析平台v2.5.0发布
2024年4月8日,DataEase开源数据可视化分析平台正式发布v2.5.0版本。 这一版本的功能升级包括:新增DataEase小助手支持,通过结合智能算法和LLM(即Large Language Model,大语言模型)能力,DataEas…...
维修伊顿触摸屏不显示工业电脑人机界面EATON XVS-430-10MPI-1-10 深圳捷达工控维修
人机界面 (HMI) XP500 工业 PC 系列 以不同的方式思考工业平板电脑 对于严酷、高要求的应用,工业平板电脑设定了可配置性和稳健性的标准。伊顿的 XP500 系列工业平板电脑凭借防刮钢化玻璃屏幕、铸铝外壳和无风扇设计满足了这些需求。这些功能使 XP500 HMI成为一款节…...
趣话最大割问题:花果山之群猴博弈
内容来源:量子前哨(ID:Qforepost) 编辑丨浪味仙 排版丨 沛贤 深度好文:3000字丨15分钟阅读 趋利避害,是所有生物遵循的自然法则,人类也不例外。 举个例子,假如你是某生鲜平台的配…...
上周面试了一个大模型算法岗的女生,有点崩溃。。。
节前,我们星球组织了一场算法岗技术&面试讨论会,邀请了一些互联网大厂朋友、参加社招和校招面试的同学,针对算法岗技术趋势、大模型落地项目经验分享、新手如何入门算法岗、该如何准备、面试常考点分享等热门话题进行了深入的讨论。 汇总…...
AI系列:大语言模型的function calling
目录 大语言模型(LLM) 的function calling实验:OpenAI之function calling序列图:function calling如何工作详情: 对话内容参考代码 后续: 使用LangChain实现function calling参考 大语言模型(LLM) 的function calling 大语言模型(LLM)可以使用自然语言与…...
conda 创建、激活、退出、删除虚拟环境
一、conda 本地环境常用操作 #获取版本号 conda --version 或 conda -V #检查更新当前conda conda update conda #查看当前存在哪些虚拟环境 conda env list 或 conda info -e #查看--安装--更新--删除包 conda list: conda search package_name# 查询包 cond…...
【Entity Framework】聊一聊EF中继承关系
【Entity Framework】聊一聊EF中继承关系 文章目录 【Entity Framework】聊一聊EF中继承关系一、概述二、实体类型层次结构映射三、每个层次结构一张表和鉴别器配置四、共享列五、每个类型一张表配置六、每个具体类型一张表配置七、TPC数据库架构八、总结 一、概述 Entity Fra…...
curaengine编译源码之libarcus编译记录
libArcus的编译(成功安装) This library contains C code and Python3 bindings for creating a socket in a thread and using this socket to send and receive messages based on the Protocol Buffers library. It is designed to facilitate the c…...
日照建站外包/龙岗百度快速排名
用了FineUI有一段时间了,还是分享下我咋改的吧,没想的那么难,我也是从小白来的。 基础是要懂JQ和EXTJS,主要是要懂JQ和EXTJS能干啥,这里有两个网站http://www.w3school.com.cn/jquery/traversing_find.asphttp://extjs…...
如何建设公司的网站/网站排名
请确保具备以下条件: Internet 连接。 计算机C盘大于6 GB 的可用空间用于下载。 8GB的U盘。建议使用空白U盘,因为其中的任何内容都将被删除。重要信息 建议在运行 Windows7 或Windows8.1 的电脑上使用介质创建工具。如果你在运行Windows10 的电脑上运行此…...
wordpress怎么改图标/百度框架户开户渠道代理
[求助]各位大哥大姐,有谁知道java连oracle thin 驱动包在那下啊各位大哥大姐:我安的是oracle8.1.5,,java我用的是jbuilderx..但是怎么也连接不上。下面是我写的代码,但是在Connection connDriverManager.getConnection(url,"internal","oracle")这里一直抛…...
做网站竞品分析/怎么在百度做宣传广告
data-dismiss"alert"——为关闭button加入该属性能够使其自己主动为警告框赋予关闭功能。 .fade .in——为警告框在关闭时加入动画效果。 很多其它细节參考演示样例: <!DOCTYPE html> <html lang"en"> <head><meta charse…...
wordpress 简单企业主题下载地址/seo关键词优化技巧
转载:http://blog.csdn.net/yzzst 今天逛CSDN看到一个投票的议题: 作为程序员的我,接私活有错么? 我艹,“我没错”以碾压性的票数94%获胜,震惊了我!!! 很多路过的程序员…...
方山网站建设/河南郑州最近的热搜事件
Python 怎么获取json 里的特定的某个值如果孤独的人愿意回头,焦躁的人愿意等候,内向的人愿意开口,也许这才是爱情最真的样子。”首先我们要导入json包,新建一个对象。 真正的爱情并不一定是他人眼中的完美匹配,而是相爱…...