当前位置: 首页 > news >正文

设计链表(不难,代码稍微多一点)

设计链表

在链表类中实现这些功能:

  • get(index):获取链表中第 index 个节点的值。如果索引无效,则返回-1。
  • addAtHead(val):在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点。
  • addAtTail(val):将值为 val 的节点追加到链表的最后一个元素。
  • addAtIndex(index,val):在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度,则该节点将附加到链表的末尾。如果 index 大于链表长度,则不会插入节点。如果index小于0,则在头部插入节点。
  • deleteAtIndex(index):如果索引 index 有效,则删除链表中的第 index 个节点。

思路

这道题目,我觉得是链表部分最好的练习链表操作的一道题目,虽然不一定是考的频率最高的。为什么这么说?

  1. 删除元素
  2. 新增元素
  3. 查询元素

上述对链表的操作都已经涉及。

类中的属性

根据题目第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)

先不考虑头尾这两个特例。

正常插入

我们先想一下在正常结点中插入数据
在这里插入图片描述

  1. 找到需要插入的前驱节点(注意一定要是前驱节点)也就是上图中C.
  2. new 一个新节点
  3. newNode的next -> 前驱节点的next
  4. 前驱节点的next -> newNode
  5. 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);}}

总结

  1. 利用虚拟节点处理 删除、更新操作。
  2. 注意get方法获取的返回的值应该是:preNode.next.val
  3. 新增节点的时候,注意下代码顺序。

相关文章:

设计链表(不难,代码稍微多一点)

设计链表 在链表类中实现这些功能&#xff1a; get(index)&#xff1a;获取链表中第 index 个节点的值。如果索引无效&#xff0c;则返回-1。addAtHead(val)&#xff1a;在链表的第一个元素之前添加一个值为 val 的节点。插入后&#xff0c;新节点将成为链表的第一个节点。ad…...

[GXYCTF2019]禁止套娃

进来发现只有这句话&#xff0c;习惯性访问一下flag.php&#xff0c;发现不是404&#xff0c;那就证明flag就在这了&#xff0c;接下来要想办法拿到flag.php的源码。 这道题是.git文件泄露网页源码&#xff0c;githack拿到index.php源码 这里观察到多次判断&#xff0c;首先要…...

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 个点的有向图&#xff0c;初始没有边&#xff0c;接下来有 q q q 次操作&#xff0c;形式如下&#xff1a; 1 u v w 表示…...

【AIGC】Stable Diffusion的采样器入门

在 Stable Diffusion 中&#xff0c;采样器&#xff08;Sampler&#xff09;是指用于生成图像的一种技术或方法&#xff0c;它决定了模型如何从潜在空间中抽样并生成图像。采样器在生成图像的过程中起着重要作用&#xff0c;影响着生成图像的多样性、质量和创造性。以下是对 St…...

【Python】通过conda安装Python的IDE

背景 系统&#xff1a;win11 软件&#xff1a;anaconda Navigator 问题现象&#xff1a;①使用Navigator安装jupyter notebook以及Spyder IDE 一直转圈。②然后进入anaconda prompt执行conda install jupyter notebook一直卡在Solving environment/-\。 类似问题&#xff1a; …...

基于HTML5实现动态烟花秀效果(含音效和文字)实战

目录 前言 一、烟花秀效果功能分解 1、功能分解 2、界面分解 二、HTML功能实现 1、html界面设计 2、背景音乐和燃放触发 3、燃放控制 4、对联展示 5、脚本引用即文本展示 三、脚本调用及实现 1、烟花燃放 2、燃放响应 3、烟花canvas创建 4、燃放声音控制 5、实际…...

「数据结构」栈和队列

栈 栈的基本概念 定义 栈是只允许在一端进行插入或删除操作的线性表栈顶&#xff1a;线性表允许进行插入删除的那一端栈底&#xff1a;固定的&#xff0c;不允许进行插入和删除的另一端空栈&#xff1a;不含任何元素特点&#xff1a;后进先出&#xff08;LIFO&#xff09; 基…...

【机器学习笔记】5 机器学习实践

数据集划分 子集划分 训练集&#xff08;Training Set&#xff09;&#xff1a;帮助我们训练模型&#xff0c;简单的说就是通过训练集的数据让我们确定拟合曲线的参数。 验证集&#xff08;Validation Set&#xff09;&#xff1a;也叫做开发集&#xff08; Dev Set &#xf…...

C++ //练习 7.5 在你的Person类中提供一些操作使其能够返回姓名和住址。这些函数是否应该是const的呢?解释原因。

C Primer&#xff08;第5版&#xff09; 练习 7.5 练习 7.5 在你的Person类中提供一些操作使其能够返回姓名和住址。这些函数是否应该是const的呢&#xff1f;解释原因。 环境&#xff1a;Linux Ubuntu&#xff08;云服务器&#xff09; 工具&#xff1a;vim 解释 姓名大概…...

python系统学习Day2

section3 python Foudamentals part one&#xff1a;data types and variables 数据类型&#xff1a;整数、浮点数、字符串、布尔值、空值 #整型&#xff0c;没有大小限制 >>>9 / 3 #3.0 >>>10 // 3 #3 地板除 >>>10 % 3 #1 取余#浮点型&#xff…...

学习笔记——ENM模拟

学习笔记——ENM模拟 文章目录 前言一、文献一1. 材料与方法1.1. 大致概念1.2. 生态模型的构建1.2.1. 数据来源&#xff1a;1.2.2. 数据处理&#xff1a;1.2.3. 模型参数优化&#xff1a; 1.3. 适生情况预测1.3.1. 预测模型构建1.3.2. 适生区划分 1.4. 模型的评估与验证 2. 结果…...

数值类型的运算方式总结

提纲1&#xff1a;常见的位运算使用场景 提纲2&#xff1a;整数类型运算时的类型溢出问题&#xff0c;产生原因以及解决办法 提纲3&#xff1a;浮点类型运算时的精度丢失问题&#xff0c;产生原因以及解决办法 数值类型&#xff08;6种&#xff09;分为&#xff1a; 整型&…...

【Redis快速入门】Redis三种集群搭建配置(主从集群、哨兵集群、分片集群)

个人名片&#xff1a; &#x1f43c;作者简介&#xff1a;一名大三在校生&#xff0c;喜欢AI编程&#x1f38b; &#x1f43b;‍❄️个人主页&#x1f947;&#xff1a;落798. &#x1f43c;个人WeChat&#xff1a;hmmwx53 &#x1f54a;️系列专栏&#xff1a;&#x1f5bc;️…...

[嵌入式系统-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应用范式

先说观点&#xff1a;关于AI应用&#xff0c;通常都会聊准召。但在安全等模糊标准的场景下&#xff0c;事实上不存在准召的定义。因此&#xff0c;AI的目标应该是尽可能的“像人”。而想要评价有多“像人”&#xff0c;就先需要将人的工作数字化。而AI Agent是能够将数字化、自…...

Stable Diffusion 模型下载:ToonYou(平涂卡通)

本文收录于《AI绘画从入门到精通》专栏,专栏总目录:点这里。 文章目录 模型介绍生成案例案例一案例二案例三案例四案例五案例六案例七案例八案例九案例十...

机器学习:分类决策树(Python)

一、各种熵的计算 entropy_utils.py import numpy as np # 数值计算 import math # 标量数据的计算class EntropyUtils:"""决策树中各种熵的计算&#xff0c;包括信息熵、信息增益、信息增益率、基尼指数。统一要求&#xff1a;按照信息增益最大、信息增益率…...

红队打靶练习: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&#xff1a;1 date: 2024-02-16 14:53:49 updated: 2024-02-16 15:08:49 categories: WriteUp&#xff1a;Cyber-Range excerpt: 主机发现、目标信息扫描、源码 js 文件泄露敏感信息、hydra 爆破邮件服务&#xff08;pop3&#xff09;、邮件泄露敏…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...

【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制

目录 节点的功能承载层&#xff08;GATT/Adv&#xff09;局限性&#xff1a; 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能&#xff0c;如 Configuration …...

上位机开发过程中的设计模式体会(1):工厂方法模式、单例模式和生成器模式

简介 在我的 QT/C 开发工作中&#xff0c;合理运用设计模式极大地提高了代码的可维护性和可扩展性。本文将分享我在实际项目中应用的三种创造型模式&#xff1a;工厂方法模式、单例模式和生成器模式。 1. 工厂模式 (Factory Pattern) 应用场景 在我的 QT 项目中曾经有一个需…...

【堆垛策略】设计方法

堆垛策略的设计是积木堆叠系统的核心&#xff0c;直接影响堆叠的稳定性、效率和容错能力。以下是分层次的堆垛策略设计方法&#xff0c;涵盖基础规则、优化算法和容错机制&#xff1a; 1. 基础堆垛规则 (1) 物理稳定性优先 重心原则&#xff1a; 大尺寸/重量积木在下&#xf…...