【数据结构】链表OJ面试题5(题库+解析)

1.前言 

前五题在这http://t.csdnimg.cn/UeggB

后三题在这http://t.csdnimg.cn/gbohQ

给定一个链表,判断链表中是否有环。http://t.csdnimg.cn/Rcdyc 

给定一个链表,返回链表开始入环的第一个结点。 如果链表无环,则返回 NULLhttp://t.csdnimg.cn/pbFiK

记录每天的刷题,继续坚持!

2.OJ题目训练

11. 给定一个链表,每个结点包含一个额外增加的随机指针,该指针可以指向链表中的任何结点或空结点。 要求返回这个链表的深度拷贝。力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

题目分析

给你一个长度为 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 作为传入参数。

这道题第一次做还是会有点理解的...但其实也不复杂

其实就是,一个正常的单链表,但是有数据位,也能有指向下一个节点位,但是多出来一个指针会随机指向此链表的如何一个节点,而我们就要对他进行一个复制。复制单链表简单,但是我们要注意,这里还增加了一个额外的指针。而且我们复制的时候随机指针还是要指向原本对应的节点。

比如:下面的d1的随机指针指向了d3,而我们新的d1节点就要指向新的d3节点

若我们直接暴力复制原链表的所有值,就会发生这种错误情况

所以此题不能暴力求解

12. 其他 。ps:链表的题当前因为难度及知识面等等原因还不适合我们当前学习,以后大家自己 下去以后 Leetcode OJ链接 + 牛客 OJ链接

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

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

相关文章

大厂的供应链域数据中台设计

关注我,紧跟本系列专栏文章,咱们下篇再续! 作者简介:魔都技术专家兼架构,多家大厂后端一线研发经验,各大技术社区头部专家博主,编程严选网创始人。具有丰富的引领团队经验,深厚业务架…

Linux 软件管理(YUM RPM)

1 YUM yum(全称为 Yellow dog Updater, Modified)是一个在Fedora和RedHat以及CentOS中的Shell前端软件包管理器。基于RPM包管理,能够从指定的服务器自动处理依赖性关系,并且一次安装所有依赖的软件包,无须繁琐地一次次…

算法学习——LeetCode力扣栈与队列篇1

算法学习——LeetCode力扣栈与队列篇1 232. 用栈实现队列 232. 用栈实现队列 - 力扣(LeetCode) 描述 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty): 实现 MyQu…

ChatGPT4 教你如何完成SQL的实践应用

对数据库的各项应用与操作都离不开SQL来对数据进行增删改查。 例如 : 有一张某公司职员信息表如下: 需求1:在公司职员信息表中,请统计各部门,各岗位下的员工人数。 如果这个SQL语句不会写或者不知道怎么操作可以交给…

Unity入门学习

目录 Unity环境搭建Unity引擎是什么软件下载和安装工程文件夹 Unity界面基础Scene场景和Hierarchy层级窗口Game游戏和Project工程Inspector和Console工具栏和父子关系 Unity工作原理反射机制和游戏场景预设体和资源包的导入导出 Unity脚本基础脚本基本规则生命周期函数Inspecto…

产品效果图为何要用渲染100农场?渲染100邀请码1a12

产品效果图很重要,它能帮助设计人员和消费者理解产品特点,是不可或缺的一步。产品效果图渲染耗时耗力,不仅慢而且容易出错,在这种情况下,使用渲染农场就成了必备选择,以目前国内最好的渲染农场渲染100为例&…

JAVA设计模式之原型模式详解

原型模式 1 原型模式介绍 定义: 原型模式(Prototype Design Pattern)用一个已经创建的实例作为原型,通过复制该原型对象来创建一个和原型对象相同的新对象。 西游记中的孙悟空 拔毛变小猴,孙悟空这种根据自己的形状复制出多个身外化身的技巧,在面向对象软件设计领…

Antd+React+react-resizable实现表格拖拽功能

1、先看效果 2、环境准备 在package.json 引入相关的依赖 "dependencies": {"antd": "^5.4.0","react-resizable": "^3.0.4",},"devDependencies": {"types/react": "^18.0.33","types…

github和gitee

github GitHub是一个面向开源及私有软件项目的托管平台,因为只支持Git作为唯一的版本库格式进行托管,故名GitHub。 github可以给提交的代码打上标签,方便版本的迭代和回退,也是一个存储代码的仓库 github工作区 gitee是gitHub的…

Oracle数据表ID自增操作

一、Oracle ID自增长功能介绍 Oracle数据库默认不支持像 SQLServer、MySQL中的自增长(auto increment)功能,即自动为每一行记录的自增长字段生成下一个值。 二、Oracle ID自增长方法 第一种,通过序列(sequence&#…

第四篇:SQL语法-DDL-数据定义语言

大年初一限定篇😀 (祝广大IT学习者、工作者0 error 0 warning!) 一,DDL数据库操作 (一)库的查询操作 1.列出所有已定义数据库 show databases; 2.查询当前所处数据库 select database(); &…

【Spring】Bean 的生命周期

一、Bean 的生命周期 Spring 其实就是一个管理 Bean 对象的工厂,它负责对象的创建,对象的销毁等 所谓的生命周期就是:对象从创建开始到最终销毁的整个过程 什么时候创建 Bean 对象?创建 Bean 对象的前后会调用什么方法&#xf…

使用python-numpy实现一个简单神经网络

目录 前言 导入numpy并初始化数据和激活函数 初始化学习率和模型参数 迭代更新模型参数(权重) 小彩蛋 前言 这篇文章,小编带大家使用python-numpy实现一个简单的三层神经网络,不使用pytorch等深度学习框架,来理解…

c#cad 创建-圆(二)

运行环境 vs2022 c# cad2016 调试成功 一、代码说明 这段代码是一个AutoCAD插件,用于在模型空间中创建一个圆形。 首先,我们需要定义一个命令类CreateCircleCommand,并在命名空间CreateCircleInCad中声明。 在CreateCircleCommand类中&a…

DNS 域名系统——应用层

目录 1 域名系统 DNS 1.1 域名系统 1.2 互联网的域名结构 1.2.1 顶级域名 TLD(Top Level Domain) (1) 国家顶级域名 nTLD (2) 通用顶级域名 gTLD (3) 基础结构域名 (infrastructure domain) 1.3 域名服务器 1.3.1 域名服务器的四种类型 (1…

电子电器架构 —— 区域控制器是未来架构的正解吗?

电子电器架构 —— 区域控制器是未来架构的正解吗? 我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师(Wechat:gongkenan2013)。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 本就是小人物,输了就是输了,不要在意别人怎么看自己。江湖一碗茶…

【数据结构】双向链表(链表实现+测试+原码)

前言 在双向链表之前,如果需要查看单链表来复习一下,链接在这里: http://t.csdnimg.cn/Ib5qS 1.双向链表 1.1 链表的分类 实际中链表的结构非常多样,以下情况组合起来就有8种链表结构: 1.1.1 单向或者双向 1.1.2 …

【技巧】PCB布局技巧:带条纹的电容

这些都是无极性电容,所以这个条纹不是极性标记。一位读者得回答正确,它代表电容卷绕时,卷绕在外层的那一极。我发现现在很少有工程师知道电容一端的条纹代表什么,也不知道条纹端和不带条纹端互换带来的不同效果。即使你从来不使用…

排序算法的时间复杂度存在下界问题

对于几种常用的排序算法,无论是归并排序、快速排序、以及更加常见的冒泡排序等,这些排序算法的时间复杂度都是大于等于O(n*lg(n))的,而这些排序算法存在一个共同的行为,那就是这些算法在对元素进行排序的时候,都会进行…

16.1 Spring框架_SpringIoC容器与Bean管理(❤❤❤❤)

16.1 Spring框架_SpringIoC容器与Bean管理 1. Spring IOC1.1 IoC控制反转 1. Spring IOC 1.1 IoC控制反转 需要自己查找3种苹果的特色,从而选择符合自己的需求 告诉水果店老板自己的口味,由老板推荐哪种苹果,省去自己查询水果特点 在java中,各种水果就是各种对象,买水果就是创…