经典OJ题:随机链表的复制

目录

题目:

本题的解图关键在于画图与看图! 

思路分析:

方法一:暴力求解法。

方法二:插入法

方法解析:

 步骤一、插入

步骤二、 处理每一个copy的randdom指针⭐————重点

步骤三、拆卸节点

代码演示:


题目:

给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:

  • val:一个表示 Node.val 的整数。
  • random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为  null 。

你的代码 只 接受原链表的头节点 head 作为传入参数。

  • 题目大意:复制一个单链表,并返回一个单链表,需要复制的单链表,它的节点结构是有一个next指针和一个random指针,next指针和普通单链表的next指针一样,但是random指针是随机指向链表内部的任意节点,或者指向NULL。
  • 现在我们要完美的复制一个这样的链表,并返回它。

题源:138. 随机链表的复制 - 力扣(LeetCode) 

本题的解图关键在于画图与看图! 

思路分析:

对于本题的关键是random指针的复制。

如何将每一个节点的random完完全全的,这是我们需要思考的问题,为此我们分为两种方法。

方法一:暴力求解法。

首先,将原链表A 完整的复制下来,当然,只是复制指针next和指针的数据。

而后,设立一个指针copy ,专门的对复制下来的链表B 进行遍历。

之后,再设置一个指针rand ,专门对原链表A进行遍历,并且对链表进行计数。

最后开始遍历,因为链表A和链表B的元素一样,所以我们再使用copy对链表B的random指向的时候,可以先使用指针rand,寻找相对因节点的rand指针指向的位置,并计数,然后将计数给指针copy,让其进行遍历。

而对于寻找相应节点的rand指针指向的位置是看节点中的数值是否一样。

缺点:如果使用了最坏的结果,所有random的指向都是尾节点位置,那么遍历之后,时间复杂度抵达了最高——O(N^2)

且,我们寻找对于节点的random指向是通过节点内的数值(元素),所以如果元素都一样,那就很难分别random要找的是那一个

方法二:插入法

我们再原链表的每一个节点后插入一个新的节点,通过节点和节点之间的联系完成random的指向复制操作,最后将每一个插入的新节点从原链表上拆除并重新组装在一起,返回最后的链表。

 

 优点:这种方法解决了上面暴力解法的效率问题,上面的暴力解法因为拷贝的链表和原链表没有联系,所以需要遍历操作。

而这种方法使得拷贝的节点处在了原节点的后面,使得拷贝节点的一切数值和指针指针都可以模仿原节点操作,也就说数值可以复制,而随机指针可以变成源节点的随机指针的next。

方法解析:

 步骤一、插入

再遍历中进行空间的开辟,并且利用遍历形成局部变量,方便之后的操作。

copy的next指向cur的next , 然后cur的next指向copy ,之后cur等于copy的next

这一步创建临时的局部变量copy空间,利用遍历将每一次遍历中创建的copy插入再原链表上。

步骤二、 处理每一个copy的randdom指针⭐

将上一步中的cur返回头节点,随后设立临时的局部指针copy 指向复制节点。

再对random进行复制之前,需要为random指向NULL的节点进行单独处理。

之后,将cur->random->next赋值与copy->random

再复制完毕后,将cur移动道copy->next的位置,也就是原链表的节点位置,而copy直接再一开始的位置设置为cur->next的位置上作为临时变量。

步骤三、拆卸节点

设置一个新的指针next,用来恢复原链表和作为临时变量使用

同时定义两个指针作为拆下来组装后的头节点和尾节点,newhead和newtail

再将cur指针返回头节点进行遍历和拆卸操作,同时设立copy指向复制节点

最后当然,需要注意,设立的newhead和newtail初始值是NULL,所以先要进行赋值,赋予copy的数值后再进行遍历拆卸的尾插操作。

代码演示:


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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

软件测试|iOS 自动化测试——技术方案、环境配置

移动端的自动化测试,最常见的是 Android 自动化测试,我个人觉得 Android 的测试优先级会更高,也更开放,更容易测试;而 iOS 相较于 Android 要安全稳定的多,但也是一个必须测试的方向,这个系列文…

OAuth 2.0实现统一认证

OAuth 2.0协议概念: OAuth 是 Open Authorization 的简写。OAuth 协议为用户资源的授权提供了一个安全的、开放而又简易的标准。与以往的授权方式不同之处是 OAuth 的授权不会使第三方触及到用户的帐号信息(如用户名与密码),即第…

开源:特殊的垄断

免责声明:本博客旨在分享我对开源策略的理解和体会,不代表任何组织或机构的立场或观点,也不构成任何商业或投资的建议或担保。本博客的内容可能存在错误或遗漏,也可能随着时间的推移而变得过时或不适用。请在使用或依赖本博客的内…

Google play的企业开发者账号比个人号上包成功率更高?

众所周知,Google play作为全球最大的Android应用市场,是开发者们推广应用的首选平台。Google play平台提供了两种账号类型:个人开发者和企业开发者,开发者们可以选择创建个人开发者账号或者企业开发者账号进行应用上架。 不过&am…

Stable Diffusion WebUI扩展sd-webui-controlnet之Canny

什么是Canny? 简单来说,Canny是计算机视觉领域的一种边缘检测算法。 关于Canny算法大家可以去看我下面这篇博客,里面详细介绍了Canny算法的原理以及代码演示。 OpenCV竟然可以这样学!成神之路终将不远(十五)_maxminval opencv-CSDN博客文章浏览阅读111次。14 图像梯度…

论文阅读——Detection Hub(cvpr2023)

Detection Hub: Unifying Object Detection Datasets via Query Adaptation on Language Embedding 一、要解决的问题 大规模数据集可以提高模型性能,但是当训练多类别单一模型时,大规模数据集不能用在目标检测任务上,因为两个困难&#xff1…

latex cite命令、款式

UTS SEDE 的 latex 模板 [1,2] 用 biblatex,默认用的引用格式是 ieee。然而 Research Foundation 的 literature review 这个作业要用 APA 7,想在保留 biblatex 的情况下区分有括号和无括号两种引用格式,即 [3] 中 \citet、\citep 的分别。 …

基于selenium的pyse自动化测试框架

介绍: pyse基于selenium(webdriver)进行了简单的二次封装,比selenium所提供的方法操作更简洁。 特点: 默认使用CSS定位,同时支持多种定位方法(id\name\class\link_text\xpath\css&#xff09…

Next.js 项目——从入门到入门(Eslint+Prettier)

Next.js官方文档地址 什么是 Next.js 这是一个用于生产环境的 React 框架。 Next.js 为您提供生产环境所需的所有功能以及最佳的开发体验:包括静态及服务器端融合渲染、 支持 TypeScript、智能化打包、 路由预取等功能,无需任何配置。 功能&#xff…

mac 安装 selenium + chrome driver

前言 使用 selenium 模拟浏览器渲染数据,需要依赖各浏览器的驱动才能完成,因此需要单独安装chrome driver 查看本地 chrome 浏览器的版本 可以看到我这里已经是 arm 架构下最新的版本了 下载对应的 chrome driver 访问下面的地址: Chrome…

C++ Concurrency in Action 2nd Edition

《C Concurrency in Action - SECOND EDITION》的中文翻译-面圈网 (mianshigee.com) C/C 学习教程源码-C/C源码推荐-面试哥 (mianshigee.com) 作者正是为C11标准引入线程库的C标准委员会成员本人!并且本书作者还编写了众多构成C标准的多线程和并发相关的提案、制定…

RHCE8 资料整理(五)

RHCE8 资料整理 第五篇 系统管理第18章 进程管理18.1 进程介绍18.2 查看进程18.3 向进程发送信号18.4 进程优先级 第19章 日志19.1 rsyslog的配置19.2 查看日志 第20章 网络时间服务器20.1 时间同步必要性20.2 配置时间服务器20.3 配置客户端 第21章 计划任务21.1 at21.2 cront…

VSCode修改主题为Eclipse 绿色护眼模式

前言 从参加开发以来,一直使用eclipse进行开发,基本官方出新版本,我都会更新。后来出来很多其他的IDE工具,我也尝试了,但他们的主题都把我劝退了,黑色主题是谁想出来?😂 字体小的时…

2023年眼镜行业分析(京东眼镜销量数据分析):市场规模同比增长26%,消费需求持续释放

随着我国经济的不断发展,电子产品不断普及,低龄及老龄人口的用眼场景不断增多,不同年龄阶段的人群有不同的视力问题,因此,视力问题人口基数也随之不断加大,由此佩戴眼镜的人群也不断增多。 同时&#xff0c…

华为eNSP实验-三层交换机的不同网段通信(通过OSPF路由方式)

1.拓扑图 2.过程如下 2.1 首先PC1和PC2配置好IP地址 2.2 在SW1上配置虚拟网关及VLAN <Huawei>system-view [Huawei]sysname SW1 [SW1]undo info-center enable [SW1] [SW1]vlan batch 10 20 [SW1]interface GigabitEthernet 0/0/1 [SW1-GigabitEthernet0/0/1]port li…

Ubuntu22.04配置Go环境

Ubuntu上配置Go环境biCentOS简单多了&#xff0c;有两种方案&#xff0c;一种直接使用apt进行安装&#xff0c;一种自己从官网下载安装包进行安装。 1、使用apt直接安装 更新apt安装包&#xff0c;常规操作 apt update 然后看看apt自带的Go版本是多少 apt list golang 是1…

Git 入门使用

一、Git 入门 1.1 Git简介 Git是一个开源的分布式版本控制系统&#xff0c;用于敏捷高效地处理任何或小或大的项目。Git是由Linus Torvalds为了帮助管理Linux内核开发而开发的一个开放源码的版本控制软件。 Git是目前世界上最先进的分布式版本控制系统&#xff0c;没有之一&a…

【自然语言处理】基于python的问答系统实现

一&#xff0c;文件准备 该问答系统是基于已知的问题和其一一对应的答案进行实现的。首先需要准备两个文本文件&#xff0c;分别命名为“question.txt”和“answer.txt”&#xff0c;分别是问题文件和答案文件&#xff0c;每一行是一个问题以及对应的答案。 问题文件: 中国的首…

vue前端实现多个url下载并合并为zip文件

一、安装 npm install jszip npm install file-saver 二、引入 import axios from axios import JSZip from "jszip"; import FileSaver from "file-saver"; 三、核心代码 videoData:[/video/26519f026fc012521605563015227403.mp4,/video/f7b9cdae14…