位置: IT常识 - 正文

没有关系的话,那就去建立关系吧(没有关系怎么表达)

编辑:rootadmin
没有关系的话,那就去建立关系吧

推荐整理分享没有关系的话,那就去建立关系吧(没有关系怎么表达),希望有所帮助,仅作参考,欢迎阅读内容。

文章相关热门搜索词:没有关系的关系说说,没有关系的话形容,没有关系的话就没关系了,没有关系的话怎么说,没有关系的话怎么表达,没有关系的话怎么说,没有关系的话,zhao句,没有关系的话形容,内容如对您有帮助,希望把文章链接给更多的朋友!

        今天给大家分享一道链表的好题--链表的深度拷贝,学会这道题,你的链表就可以达到优秀的水平了。力扣

         先来理解一下题目意思,即建立一个新的单向链表,里面每个结点的值与对应的原链表相同,并且random指针也要指向新链表中与原链表对应的那个相对位置。(即假设原链表中的第一个结点的random指向原链表的最后一个结点,那么新链表的第一个结点也要指向新链表的最后一个结点,即random指针是链表内部确定相对位置的一个指针)。

        首先,拷贝一个新的链表,其对应结点的值与原链表对应结点的值相同是很容易实现的。可以用一个cur指针遍历原链表,然后建立一个新链表头,然后逐个尾插既可。   

struct Node* cur=head; struct Node* newhead = NULL; struct Node* tail = NULL; while(cur) { //每次尾插都需要一个新结点,其val与原链表对应相等 struct Node* newnode = (struct Node*)malloc(sizeof(struct Node)); //第一次尾插时 if(NULL ==tail) { newhead = tail =newnode; newnode->val = cur->val; newnode->next = newnode->random = NULL; } //后续尾插 else { tail->next = newnode; tail = tail->next; } //拷贝一个新结点后,cur往后走 cur = ucr->next; }

此时,只是完成了next链接和val拷贝,random的指向还没有拷贝。

暴力求解O(N^2)

可以建立一个结构体的指针数组   struct Node* arr[n]  n为原链表中的结点数

struct Node* arr[n]; int count = 0; while(cur) { arr[count] = cur->random; count++; cur =cur->next; }

再次利用cur遍历原链表,将每个结点的random保存在创建的结构体指针数组 arr中。

struct Node* newcur=newhead; int newcount=-1; while(newcur) { ++newcount;//每次进来都拿到原链表的一个random struct Node* tmp = arr[newcount];//用tmp保存这个random cur = head; while(cur != tmp) { //遍历原链表,看看此时的random是原链表的第几个结点 count++; } //找到新链表中对应的第count个结点 struct Node* find = newhead; while(count--) { //一共走count步 newhead = newhead->next; } //找到了newcur位置的random的指向 newcur->random = find; //newcur继续往后走 newcur = newcur->next; }

暴力解法虽然也能解决问题,但是时间复杂度为O(N^2),效率低,不推荐。

更优解O(N)

        通过暴力解法我们可以发现,寻找random指向的难点在于它是随机的,如果想要确定具体的相对位置(相对于头是第几个)则必须经过2次遍历,那么怎样简化寻找相对位置的过程呢?

没有关系的话,那就去建立关系吧(没有关系怎么表达)

        想一下random的关系在哪里出现,应该只有原链表中,而我们又想要建立新链表中random的关系,因此我们必须建立原链表与新链表直接的关系,通过原链表的random找到新链表的random。

        再借助next指针思考,我们可以将新链表对应的结点连接到原链表上。

        

 此时逻辑一下子清晰了,每个新结点都在原对应结点的next位置。

例如:对于13这个结点的random连接,新13->random = 原13->random->next,即通过原链表random的查找方式,再加上next,来连接新链表的random。

具体的实现过程分为3个方面。

1、连接原、新链表 struct Node* cur=head; while(cur) { //建立新结点并初始化 struct Node* newnode = (struct Node*)malloc(sizeof(struct Node)); newnode->next = newnode->random =NULL; random->val = cur->val; //先保存一下原结点的下一个结点 struct Node* next = cur->next; //将新结点连接到原链表 cur->next = newnode; newnode->next = next; //cur继续往后走 cur = next; }2、建立新链表的random联系 cur = head; while(cur) { //确保cur不为NULL,再建立copy指向cur的next struct Node* copy = cur->next; //建立copy的random联系时,要确保其不为空,否则不能进行next操作 //因此这里讨论一下原链表的random是否为空 if(NULL == cur->random) { copy->random = NULL; } else { copy-> random = cur->random->next; } //连接后cur继续往后走 cur = copy->next; }

要注意,copy指针和cur指针移动的位置,可以理解为cur不为空时,建立copy指向此时cur的下一个,完成相关连接后copy丢弃,cur往后走,copy只起到临时变量的作用(连接后便丢弃)。

3、分离原、新链表

分离的过程直接将copy部分的结点尾插到一个新结点即可

struct Node* newhead=NULL,*tail=NULL; cur=head; while(cur) { struct Node* copy = cur->next; struct Node* next = copy->next; if(NULL == tail)//第一次尾插 { newhead = tail =copy; } else//后续尾插 { tail->next = copy; //tail往后走,指向新的最后一个结点 tail = tail->next; } //分离原链表,cur继续往后走 cur->next=next; cur= next; } return newhead;

这部分要注意,else内部tail往下走是后续尾插才有的操作。

总结:为了优化代码,使时间复杂度变为O(N),必须建立原来链表的新链表直接的联系,借助原链表的random->next,来连接新链表的random。

所以说,没有关系的话,那就去勇敢的建立关系吧。

本文链接地址:https://www.jiuchutong.com/zhishi/298428.html 转载请保留说明!

上一篇:Vue3中的父传子和子传父如何实现(vue3父子传值)

下一篇:结合表单验证谈el-form中model、prop、rules属性(表单验证用什么方法实现)

  • vivo原子隐私系统怎么打开(vivo 原子)

    vivo原子隐私系统怎么打开(vivo 原子)

  • 搜狗输入法怎么调出全角半角(搜狗输入法怎么删除记忆词汇)

    搜狗输入法怎么调出全角半角(搜狗输入法怎么删除记忆词汇)

  • 小米10怎么看是不是三星屏幕(小米10怎么看是三星屏幕还是华星光电屏幕)

    小米10怎么看是不是三星屏幕(小米10怎么看是三星屏幕还是华星光电屏幕)

  • 华为右上角图标指南针(华为右上角图标两个勾)

    华为右上角图标指南针(华为右上角图标两个勾)

  • word中编号和文字距离太大怎么办(word编号和文字间距太大)

    word中编号和文字距离太大怎么办(word编号和文字间距太大)

  • iphone双击home键分屏有什么用(iphone双击home键反应变慢)

    iphone双击home键分屏有什么用(iphone双击home键反应变慢)

  • 华为nova7耳塞插哪里(华为nova7的耳塞怎么没有声音)

    华为nova7耳塞插哪里(华为nova7的耳塞怎么没有声音)

  • 钉钉视频是全部人都能看到吗(钉钉视频清楚吗)

    钉钉视频是全部人都能看到吗(钉钉视频清楚吗)

  • airpods坏了怎么保修(airpods坏了怎么换)

    airpods坏了怎么保修(airpods坏了怎么换)

  • 华为nova7pro有nfc功能吗(华为nova7pro有没有红外线)

    华为nova7pro有nfc功能吗(华为nova7pro有没有红外线)

  • oppo手机左上角显示hd怎么关掉(oppo手机左上角有个黑圈怎么回事)

    oppo手机左上角显示hd怎么关掉(oppo手机左上角有个黑圈怎么回事)

  • 苹果样机和新机的区别(苹果样机和新机哪个好)

    苹果样机和新机的区别(苹果样机和新机哪个好)

  • 耳机老是自动打开音乐怎么办(耳机老是自动打开语音控制)

    耳机老是自动打开音乐怎么办(耳机老是自动打开语音控制)

  • 华为青山黛是什么材质(华为青山黛是什么颜色)

    华为青山黛是什么材质(华为青山黛是什么颜色)

  • 怎么查看淘宝极速退款(怎么查看淘宝极速退款次数多少)

    怎么查看淘宝极速退款(怎么查看淘宝极速退款次数多少)

  • 128gb与128g哪个内存大(128gb跟128g有啥区别)

    128gb与128g哪个内存大(128gb跟128g有啥区别)

  • 手机充电头松了怎么办(手机充电头松了更换尾插要多少钱)

    手机充电头松了怎么办(手机充电头松了更换尾插要多少钱)

  • 段落文字框不可以进行的操作是(段落文字框不可用怎么办)

    段落文字框不可以进行的操作是(段落文字框不可用怎么办)

  • 苹果11pro max夜景模式怎么使用(苹果11pro max夜景模式)

    苹果11pro max夜景模式怎么使用(苹果11pro max夜景模式)

  • 未信任的app怎么设置(未信任的软件怎么信任)

    未信任的app怎么设置(未信任的软件怎么信任)

  • 腾讯课堂下载的视频在哪个文件夹(腾讯课堂app下载安装)

    腾讯课堂下载的视频在哪个文件夹(腾讯课堂app下载安装)

  • 微信对方发来的视频提示音能静音吗(微信对方发来的验证消息显示不完)

    微信对方发来的视频提示音能静音吗(微信对方发来的验证消息显示不完)

  • 前端综合项目-个人博客网页设计(前端项目实战教程)

    前端综合项目-个人博客网页设计(前端项目实战教程)

  • YOLOv5源码逐行超详细注释与解读(6)——网络结构(1)yolo.py(yolov1 实现)

    YOLOv5源码逐行超详细注释与解读(6)——网络结构(1)yolo.py(yolov1 实现)

  • 税中税是多少
  • 车险 保险金额
  • 公账的钱取现金
  • 小规模纳税人怎么转成一般纳税人
  • 发票怎么看开票最大额
  • 会议服务费怎么开
  • 500元以内的无票报销是累计还是一次
  • 取得不动产权证书时间是指哪个时间
  • 土地出让金计算方法
  • 借款利息支出全部可以税前扣除吗
  • 零售不要发票如何报税
  • 官司赔偿费用需要发票吗
  • 公司购买住宅可以分期付款吗
  • 电子发票详见清单怎么开
  • 企业房租收入营改增
  • 个人营业执照怎么注销网上申请流程
  • 无形资产摊销表模板
  • 在职员工 开公司
  • 不动产权时间怎么确认
  • 闲置资金的利息收益要冲减财务费用
  • 直接转让土地使用权 土地增值税申报表
  • 企业向个人赠送礼品
  • 开具的电子发票需要打印出来做账吗
  • win11桌面图标如何固定不动
  • 资产负债比和资产负债率
  • 运输费计入什么会计分录
  • 如何加快身体的新陈代谢
  • 新成立公司工会经费什么时候交
  • macbookappstore未知错误
  • 仓储费计入存货成本吗
  • wordpress介绍
  • 生产性生物资产折旧计入什么科目
  • 奥林匹克森林公园奥海
  • Laravel 5.4向IoC容器中添加自定义类的方法示例
  • 增值税发票认证抵扣时间规定
  • 学习笔记:深度学习(2)——BP神经网络
  • 个体工商户和个人独资企业的区别
  • 在建工程转固定资产摘要怎么写
  • 社保代扣代缴的规定
  • 劳务派遣合法吗
  • 小微企业免征增值税优惠政策
  • 为什么合理损耗不计入成本
  • 房地产企业怎么预缴企业所得税
  • 应收票据的核算范围包括
  • 预付账款借方如何结转
  • 销售返利的会计处理方法
  • 仓库费用计入什么科目
  • 股东分红算不算成本费用
  • 报关单填制的运费怎么算
  • 赠送给客户的商品怎么做会计分录
  • 超市会计怎么做会计分录
  • MySQL Index Condition Pushdown(ICP)性能优化方法实例
  • 电脑主机windows 7
  • win8和win10双系统安装教程
  • Win10 64位正式版系统安装方法全过程图解(U大师)
  • Linux系统中文件的文件名存储在文件所在的目录
  • 电脑重装win7系统黑屏
  • win10累积更新是什么意思
  • mmc.exe是什么
  • win7安装kb4534310补丁失败
  • win7系统怎么设置屏保
  • 在linux操作系统中
  • cocos2d-x教程
  • 游戏开发unity3d
  • unity碰撞得分代码
  • bash 删除文件夹
  • 值得收藏的十大收录机
  • node.js开发微信小程序
  • android的图片文件保存在工程的哪个文件夹
  • unityugui
  • 侧边栏html
  • pythonsetter
  • 税务登记注销证明是什么样的
  • 双定户如何网上申报
  • 税务部门的扣款协议
  • 纳税申报期过了怎么处理
  • 石油产品消费税征收
  • 海关进口增值税专用缴款书在哪里打印
  • 中国民营经济十大新闻人物
  • 收缴和缴纳的区别
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

    网站地图: 企业信息 工商信息 财税知识 网络常识 编程技术

    友情链接: 武汉网站建设