设计链表(不难,代码稍微多一点)
设计链表
在链表类中实现这些功能:
- get(index):获取链表中第 index 个节点的值。如果索引无效,则返回-1。
- addAtHead(val):在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点。
- addAtTail(val):将值为 val 的节点追加到链表的最后一个元素。
- addAtIndex(index,val):在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度,则该节点将附加到链表的末尾。如果 index 大于链表长度,则不会插入节点。如果index小于0,则在头部插入节点。
- deleteAtIndex(index):如果索引 index 有效,则删除链表中的第 index 个节点。
思路
这道题目,我觉得是链表部分最好的练习链表操作的一道题目,虽然不一定是考的频率最高的。为什么这么说?
- 删除元素
- 新增元素
- 查询元素
上述对链表的操作都已经涉及。
类中的属性
根据题目第4点要求,我们可以知道,这个自定义链表中一定有个 size 属性,记录当前链表的长度。(不然你怎么判断index?)
根据上一篇文章移除链表元素我们可以知道,这里需要一个虚拟头结点来处理删除操作。
各个方法的代码
分析一下 addAtHead() 和 addAtTail()可以合并到 addAtIndex()方法中
大概就是:
addAtHead(val) == addAtIndex(0,val)
addAtTail(val) == addAtIndex(size,val)
所以,我们真正需要写的方法只有 get(index)、deleteAtIndex(index)、 addAtIndex(index,val)三个方法。我们先从难的开始
addAtIndex(index,val)
先不考虑头尾这两个特例。
正常插入
我们先想一下在正常结点中插入数据

- 找到需要插入的前驱节点(注意一定要是前驱节点)也就是上图中C.
- new 一个新节点
- newNode的next -> 前驱节点的next
- 前驱节点的next -> newNode
- size++
插入头(head)
我们这里使用的虚拟节点,采用上述方法可以直接插入
插入尾(tail)
仔细一想,好像也可以,没问题。
相关代码:
public void addAtIndex(int index,int val) {if (index > size) {return;} else if (index <= 0) {index = 0;}ListNode newLinedList = new ListNode(val);ListNode preNode = head;for (int i = 0; i < index; i++) {preNode = preNode.next;}//这一步很重要,顺序不能反。//一定是新节点先指向下一个,然后再断开前驱节点的nextnewLinedList.next = preNode.next;preNode.next = newLinedList;size++;}
话说回来,因为我们是用size+ 虚拟头节点,所以插入头、尾只是size的值不同,所以不会有什么特殊处理的地方。删除操作也是一样。
deleteAtIndex(index)

遍历到需要删除的节点的前驱节点(黑人问号脸?又是前驱节点?大家可以想一下,为什么不管是新增还是删除都需要前驱节点)
删除很简单 :伪代码: preNode.next = preNode.next.next
实际代码:
public void deleteAtIndex(int index) {if (index < 0 || index >= size) {return;}ListNode dummyHead = head;for (int i = 0; i < index; i++) {dummyHead = dummyHead.next;}//删除节点dummyHead.next = dummyHead.next.next;size--;}
get(index)
get其实和删除差不多,但是唯一需要注意的是,我们是虚拟头结点,所以在遍历获取到的节点是前驱节点,返回的是 preNode.next.val
代码:
public int get(int index) {//这里需要带等号if (index < 0 || index >= size) {return -1;}ListNode dummyHead = head;for (int i = 0; i < index; i++) {dummyHead = dummyHead.next;}//注意是虚拟头结点,所以需要返回next.valreturn dummyHead.next.val;}
代码
public class MyLinkedList {/*** 虚拟头结点*/ListNode head;int size;MyLinkedList() {size = 0;head = new ListNode(0);}public void addAtIndex(int index, int val) {if (index > size) {return;} else if (index <= 0) {index = 0;}ListNode newLinedList = new ListNode(val);ListNode preNode = head;for (int i = 0; i < index; i++) {preNode = preNode.next;}//这一步很重要,顺序不能反。//一定是新节点先指向下一个,然后再断开前驱节点的nextnewLinedList.next = preNode.next;preNode.next = newLinedList;size++;}public int get(int index) {//这里需要带等号if (index < 0 || index >= size) {return -1;}ListNode dummyHead = head;for (int i = 0; i < index; i++) {dummyHead = dummyHead.next;}//注意是虚拟头结点,所以需要返回next.valreturn dummyHead.next.val;}public void deleteAtIndex(int index) {if (index < 0 || index >= size) {return;}ListNode dummyHead = head;for (int i = 0; i < index; i++) {dummyHead = dummyHead.next;}//删除节点dummyHead.next = dummyHead.next.next;size--;}public void addAtHead(int val) {addAtIndex(0, val);}public void addAtTail(int val) {addAtIndex(size, val);}}
总结
- 利用虚拟节点处理 删除、更新操作。
- 注意get方法获取的返回的值应该是:
preNode.next.val。 - 新增节点的时候,注意下代码顺序。
相关文章:
设计链表(不难,代码稍微多一点)
设计链表 在链表类中实现这些功能: get(index):获取链表中第 index 个节点的值。如果索引无效,则返回-1。addAtHead(val):在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点。ad…...
[GXYCTF2019]禁止套娃
进来发现只有这句话,习惯性访问一下flag.php,发现不是404,那就证明flag就在这了,接下来要想办法拿到flag.php的源码。 这道题是.git文件泄露网页源码,githack拿到index.php源码 这里观察到多次判断,首先要…...
ubuntu下如何查看显卡及显卡驱动
ubuntu下如何查看显卡及显卡驱动 使用nvidia-smi 工具查看 查看显卡型号nvida-smi -L $ nvidia-smi -L GPU 0: NVIDIA GeForce RTX 3050 4GB Laptop GPU (UUID: GPU-4cf7b7cb-f103-bf56-2d59-304f8996e28c)当然直接使用nvida-smi 命令可以查看更多信息 $ nvidia-smi Mon Fe…...
【图论经典题目讲解】CF786B - Legacy 一道线段树优化建图的经典题目
C F 786 B − L e g a c y \mathrm{CF786B - Legacy} CF786B−Legacy D e s c r i p t i o n \mathrm{Description} Description 给定 1 1 1 张 n n n 个点的有向图,初始没有边,接下来有 q q q 次操作,形式如下: 1 u v w 表示…...
【AIGC】Stable Diffusion的采样器入门
在 Stable Diffusion 中,采样器(Sampler)是指用于生成图像的一种技术或方法,它决定了模型如何从潜在空间中抽样并生成图像。采样器在生成图像的过程中起着重要作用,影响着生成图像的多样性、质量和创造性。以下是对 St…...
【Python】通过conda安装Python的IDE
背景 系统:win11 软件:anaconda Navigator 问题现象:①使用Navigator安装jupyter notebook以及Spyder IDE 一直转圈。②然后进入anaconda prompt执行conda install jupyter notebook一直卡在Solving environment/-\。 类似问题: …...
基于HTML5实现动态烟花秀效果(含音效和文字)实战
目录 前言 一、烟花秀效果功能分解 1、功能分解 2、界面分解 二、HTML功能实现 1、html界面设计 2、背景音乐和燃放触发 3、燃放控制 4、对联展示 5、脚本引用即文本展示 三、脚本调用及实现 1、烟花燃放 2、燃放响应 3、烟花canvas创建 4、燃放声音控制 5、实际…...
「数据结构」栈和队列
栈 栈的基本概念 定义 栈是只允许在一端进行插入或删除操作的线性表栈顶:线性表允许进行插入删除的那一端栈底:固定的,不允许进行插入和删除的另一端空栈:不含任何元素特点:后进先出(LIFO) 基…...
【机器学习笔记】5 机器学习实践
数据集划分 子集划分 训练集(Training Set):帮助我们训练模型,简单的说就是通过训练集的数据让我们确定拟合曲线的参数。 验证集(Validation Set):也叫做开发集( Dev Set …...
C++ //练习 7.5 在你的Person类中提供一些操作使其能够返回姓名和住址。这些函数是否应该是const的呢?解释原因。
C Primer(第5版) 练习 7.5 练习 7.5 在你的Person类中提供一些操作使其能够返回姓名和住址。这些函数是否应该是const的呢?解释原因。 环境:Linux Ubuntu(云服务器) 工具:vim 解释 姓名大概…...
python系统学习Day2
section3 python Foudamentals part one:data types and variables 数据类型:整数、浮点数、字符串、布尔值、空值 #整型,没有大小限制 >>>9 / 3 #3.0 >>>10 // 3 #3 地板除 >>>10 % 3 #1 取余#浮点型ÿ…...
学习笔记——ENM模拟
学习笔记——ENM模拟 文章目录 前言一、文献一1. 材料与方法1.1. 大致概念1.2. 生态模型的构建1.2.1. 数据来源:1.2.2. 数据处理:1.2.3. 模型参数优化: 1.3. 适生情况预测1.3.1. 预测模型构建1.3.2. 适生区划分 1.4. 模型的评估与验证 2. 结果…...
数值类型的运算方式总结
提纲1:常见的位运算使用场景 提纲2:整数类型运算时的类型溢出问题,产生原因以及解决办法 提纲3:浮点类型运算时的精度丢失问题,产生原因以及解决办法 数值类型(6种)分为: 整型&…...
【Redis快速入门】Redis三种集群搭建配置(主从集群、哨兵集群、分片集群)
个人名片: 🐼作者简介:一名大三在校生,喜欢AI编程🎋 🐻❄️个人主页🥇:落798. 🐼个人WeChat:hmmwx53 🕊️系列专栏:🖼️…...
[嵌入式系统-14]:常见实时嵌入式操作系统比较:RT-Thread、uC/OS-II和FreeRTOS、Linux
目录 一、实时嵌入式操作系统 1.1 概述 1.2 什么“实时” 1.3 什么是硬实时和软实时 1.4 什么是嵌入式 1.5 什么操作系统 二、常见重量级操作系统 三、常见轻量级嵌入式操作系统 3.1 概述 3.2 FreeRTOS 3.3 uC/OS-II 3.4 RT-Thread 3.5 RT-Thread、uC/OS-II、Free…...
基于AI Agent探讨:安全领域下的AI应用范式
先说观点:关于AI应用,通常都会聊准召。但在安全等模糊标准的场景下,事实上不存在准召的定义。因此,AI的目标应该是尽可能的“像人”。而想要评价有多“像人”,就先需要将人的工作数字化。而AI Agent是能够将数字化、自…...
Stable Diffusion 模型下载:ToonYou(平涂卡通)
本文收录于《AI绘画从入门到精通》专栏,专栏总目录:点这里。 文章目录 模型介绍生成案例案例一案例二案例三案例四案例五案例六案例七案例八案例九案例十...
机器学习:分类决策树(Python)
一、各种熵的计算 entropy_utils.py import numpy as np # 数值计算 import math # 标量数据的计算class EntropyUtils:"""决策树中各种熵的计算,包括信息熵、信息增益、信息增益率、基尼指数。统一要求:按照信息增益最大、信息增益率…...
红队打靶练习:HACK ME PLEASE: 1
信息收集 1、arp ┌──(root㉿ru)-[~/kali] └─# arp-scan -l Interface: eth0, type: EN10MB, MAC: 00:0c:29:69:c7:bf, IPv4: 192.168.61.128 Starting arp-scan 1.10.0 with 256 hosts (https://github.com/royhills/arp-scan) 192.168.61.2 00:50:56:f0:df:20 …...
《VulnHub》GoldenEye:1
title: 《VulnHub》GoldenEye:1 date: 2024-02-16 14:53:49 updated: 2024-02-16 15:08:49 categories: WriteUp:Cyber-Range excerpt: 主机发现、目标信息扫描、源码 js 文件泄露敏感信息、hydra 爆破邮件服务(pop3)、邮件泄露敏…...
【杂谈】-递归进化:人工智能的自我改进与监管挑战
递归进化:人工智能的自我改进与监管挑战 文章目录 递归进化:人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管?3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...
【git】把本地更改提交远程新分支feature_g
创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...
相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...
ip子接口配置及删除
配置永久生效的子接口,2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...
Typeerror: cannot read properties of undefined (reading ‘XXX‘)
最近需要在离线机器上运行软件,所以得把软件用docker打包起来,大部分功能都没问题,出了一个奇怪的事情。同样的代码,在本机上用vscode可以运行起来,但是打包之后在docker里出现了问题。使用的是dialog组件,…...
JS手写代码篇----使用Promise封装AJAX请求
15、使用Promise封装AJAX请求 promise就有reject和resolve了,就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...
Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)
引言 工欲善其事,必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后,我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集,就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...
毫米波雷达基础理论(3D+4D)
3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文: 一文入门汽车毫米波雷达基本原理 :https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...
0x-3-Oracle 23 ai-sqlcl 25.1 集成安装-配置和优化
是不是受够了安装了oracle database之后sqlplus的简陋,无法删除无法上下翻页的苦恼。 可以安装readline和rlwrap插件的话,配置.bahs_profile后也能解决上下翻页这些,但是很多生产环境无法安装rpm包。 oracle提供了sqlcl免费许可,…...
