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

leetcode707 设计链表 带有输入和输出的

题目: 设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性:val 和 next。val 是当前节点的值,next 是指向下一个节点的指针/引用。如果要使用双向链表,则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

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

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

示例:

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3
linkedList.get(1); //返回2
linkedList.deleteAtIndex(1); //现在链表是1-> 3
linkedList.get(1); //返回3

思路:创建MyLinkedList 类,在类中创建ListNode 结构体,结构体中创建两个成员变量,并创建初始化的构造函数,创建成员变量size和哨兵节点,在MyLinkedList构造函数中初始化size和哨兵节点,在删除元素时,应该找到删除索引位置的前一个位置,再删除元素。
代码

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
class MyLinkedList {
public://定义链表结点结构体struct ListNode {int val;//结构体的成员变量:整数类型的valListNode* next;//结构体的成员变量:指向另一个ListNode对象的指针next//用于初始化节点的值和指向下一个节点的指针,这个构造函数在创建新结点时被调用,// 从而避免了在创建新节点后手动初始化节点的值和指针ListNode(int val) :val(val), next(nullptr) {}};//初始化链表MyLinkedList() {_size = 0;//初始化为一个ListNode对象,并且该节点的val成员变量被设置为0//用于表示虚拟头节点的默认值_dummyHead = new ListNode(0);}//使用尾插法先插入元素void addAtTail(int val) {//创建一个新节点ListNode* newNode = new ListNode(val);//从虚拟头节点开始遍历,找到链表的最后一个节点ListNode* curr = _dummyHead;while (curr->next) {curr = curr->next;}curr->next = newNode;_size++;//更新链表的大小}//获取到第index个节点数值,如果index是非法数值直接返回-1, //注意index是从0开始的,第0个节点就是头结点int get(int index) {if (index>_size-1||_size<0) {return -1;}ListNode* cur = _dummyHead->next;while (index) { cur = cur->next;index--;}return cur->val;}//在链表最前面插入一个节点,插入完成后,新插入的节点为链表的新的头节点void addAtHead(int val) {ListNode* NewNode = new ListNode(val);NewNode->next = _dummyHead->next;_dummyHead->next = NewNode;_size++;}// 在第index个节点之前插入一个新节点,例如index为0,// 那么新插入的节点为链表的新头节点。// 如果index 等于链表的长度,则说明是新插入的节点为链表的尾结点// 如果index大于链表的长度,则返回空// 如果index小于0,则在头部插入节点void addAtIndex(int index,int val) {if (index > _size)return;if (index < 0)index = 0;ListNode* newNode = new ListNode(val);ListNode* cur = _dummyHead;while (index) {cur = cur->next;index--;}newNode->next = cur->next;cur->next = newNode;_size++;}// 删除第index个节点,如果index 大于等于链表的长度,直接return,//注意index是从0开始的void deleteAtIndex(int index) {if (index >= _size||index<0)return;ListNode* cur = _dummyHead;while (index) {cur = cur->next;index--;}ListNode* tmp = cur->next;cur->next = cur->next->next;delete tmp;_size--;}void printl() {ListNode* cur = _dummyHead->next;while (cur) {cout << cur->val << "->";cur = cur->next;}cout << "NULL" << endl;cout <<"总元素个数为:" << _size;}
private:int _size;ListNode* _dummyHead;
};
int main() {MyLinkedList linkedList;linkedList.addAtTail(100);linkedList.addAtTail(200);linkedList.addAtTail(300);linkedList.addAtHead(66);linkedList.addAtIndex(1, 88);linkedList.deleteAtIndex(3);linkedList.printl();return 0;
}

相关文章:

leetcode707 设计链表 带有输入和输出的

题目&#xff1a; 设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性&#xff1a;val 和 next。val 是当前节点的值&#xff0c;next 是指向下一个节点的指针/引用。如果要使用双向链表&#xff0c;则还需要一个属性 prev 以指示链表中的上一个节…...

100种思维模型之非sr思维模型-012

什么是sr? sr是stimulus-response的缩写&#xff0c;意思是刺激反应。 那么非sr思维模型就是非刺激反应思维模型的意思。 今天我们来聊聊非sr思维模型——一个提醒我们思考&#xff0c;提醒我们任何时刻都有选择权的思维模型。 本文依然从三个方面进行介绍&#xff0c;何谓…...

绿竹生物再冲刺港交所上市:暂未商业化,孔健夫妇为实控人

近日&#xff0c;北京绿竹生物技术股份有限公司&#xff08;下称“绿竹生物”&#xff09;在港交所递交招股书&#xff0c;准备在港交所主板上市&#xff0c;中金公司为其独家保荐人。据贝多财经了解&#xff0c;绿竹生物曾于2022年6月28日在港交所递表。 相较于此前招股书&am…...

加拿大MSB金融牌照申请方案

什么是加拿大MSB金融牌照&#xff1f; 根据犯罪所得&#xff08;洗钱&#xff09;和恐怖主义融资法案&#xff0c;您的企业必须在加拿大金融交易和报告分析中心 (FINTRAC) 注册成为货币服务企业。自 2020 年 6 月 1 日起&#xff0c;外国货币服务企业也必须在 FINTRAC 注册&…...

javaEE 初阶 — 滑动窗口

文章目录滑动窗口1 滑动窗口下如何处理丢包TCP 工作机制&#xff1a;确认应答机制 超时重传机制 连接管理机制 滑动窗口 确认应答机制、超时重传机制、连接管理机制 都是给 TCP 的可靠性提供支持的。 虽然事变的比较可靠了&#xff0c;但是是有牺牲的&#xff0c;那就是传输…...

大咖说·图书分享|狼书(卷3):Node.js高级技术

Node.js都有哪些需要掌握的高级技术&#xff1f;前端为什么同样需要学习&#xff1f; Node.js未来的发展趋势究竟如何&#xff1f;本期大咖说&#xff0c;Node布道师桑世龙携新作《狼书(卷3)&#xff1a;Node.js高级技术》展开分享。 ● 嘉宾介绍 桑世龙&#xff1a;Node布道…...

1.5配置NBMA和P2MP网络类型

1.3.3实验5:配置NBMA和P2MP网络类型 1. 实验需求 控制OSPF DR的选举修改OSPF的网络类型2. 实验拓扑 配置NBMA和P2MP网络类型实验拓扑如图1-13所示。 图1-13 配置NBMA和P2MP网络类型 3. 实验步骤 帧中继的配置如图1-14和图1-15所示...

Java面试题

三次握手&#xff0c;四次挥手中&#xff0c;为什么要挥手四次 第一次握手&#xff0c;客户端发送同步报文到服务端&#xff0c;客户端知道自己有发送数据能力&#xff0c;不知道服务端是否有发送、接受数据能力。 第二次握手&#xff0c;服务端收到同步报文&#xff0c;并回复…...

opencv锁定鼠标定位

大家好&#xff0c;我是csdn的博主&#xff1a;lqj_本人 这是我的个人博客主页&#xff1a; lqj_本人的博客_CSDN博客-微信小程序,前端,python领域博主lqj_本人擅长微信小程序,前端,python,等方面的知识https://blog.csdn.net/lbcyllqj?spm1011.2415.3001.5343哔哩哔哩欢迎关注…...

机器连接和边缘计算

以一种高效、可扩展的方式进行连接和边缘计算的结合&#xff0c;解决了在工业物联网应用中的机器数据集成问题。 一 边缘计算 边缘计算描述了由中央平台管理的数据分散式处理。边缘计算对于工业物联网而言非常重要。在许多应用程序中&#xff0c;由于数据量非常大&#xff0c;…...

利用NGROK将本地网站发布为一个公开网站

一般与第三方服务集成时&#xff0c;需要提供https的回调URL&#xff0c;本地开发阶段可以利用NGROK将本地网站发布为公开的https网站。https://ngrok.com/downloadWindow下载地址&#xff1a;https://bin.equinox.io/c/bNyj1mQVY4c/ngrok-v3-stable-windows-amd64.zip以Window…...

Vulnhub 渗透练习(一)—— Breach 1.0

环境搭建 环境下载&#xff1a; https://www.vulnhub.com/entry/breach-1,152/ 环境描述&#xff1a; Vulnhub 中对此环境的描述&#xff1a; VM 配置有静态 IP 地址 (192.168.110.140)&#xff0c;因此您需要将仅主机适配器配置到该子网。 这里我用的是 VMware &#xff0…...

初探Spring采用Spring配置文件管理Bean

文章目录Spring容器演示--采用Spring配置文件管理Bean&#xff08;一&#xff09;创建Maven项目&#xff08;二&#xff09;添加Spring依赖&#xff08;三&#xff09;创建杀龙任务类&#xff08;四&#xff09;创建勇敢骑士类&#xff08;五&#xff09;采用传统方式让勇敢骑士…...

【手写 Vuex 源码】第十二篇 - Vuex 插件机制的实现

一&#xff0c;前言 上一篇&#xff0c;主要介绍了 Vuex 插件的开发&#xff0c;主要涉及以下几个点&#xff1a; Vuex 插件的使用介绍&#xff1b;Vuex 插件开发和使用分析&#xff1b;Vuex 插件机制的分析&#xff1b; 本篇&#xff0c;继续介绍 Vuex 插件机制的实现&…...

图像去噪技术简述

随着每天拍摄的数字图像数量激增&#xff0c;对更准确、更美观的图像的需求也在增加。然而&#xff0c;现代相机拍摄的图像不可避免地会受到噪声的影响&#xff0c;从而导致视觉图像质量下降。因此&#xff0c;需要在不丢失图像特征&#xff08;边缘、角和其他尖锐结构&#xf…...

数据迁移——技术选型

日常我们在开发中&#xff0c;随着业务需求的变更&#xff0c;重构系统是很常见的事情。重构系统常见的一个场景是变更底层数据模型与存储结构。这种情况下就要对数据进行迁移&#xff0c;从而使业务能正常支行。 背景如下&#xff1a;老系统中使用了mongo数据库&#xff0c;由…...

第二十七章 java并发常见知识内容(CompletableFuture)

JAVA重要知识点CompletableFuture常见函数式编程操作创建 CompletableFuture静态工厂方法处理异步结算的结果异常处理组合 CompletableFuturethenCompose() 和 thenCombine() 区别并行运行多个 CompletableFutureCompletableFuture Java 8 才被引入的一个非常有用的用于异步编…...

Qt扫盲-QMake 使用概述

QMake 使用概述一、概述二、简单开始三、使应用程序可调试1. 添加平台特定的源文件2. 如果文件不存在&#xff0c;停止qmake3. 检查多个条件一、概述 本教程教你qmake的基础知识。qmake 其实就是一个自动化编译的流程控制文件&#xff0c;也是Qt程序的生成makefile的工具&…...

Spring Cloud之Zuul

目录 简介 Zuul中的过滤器 过滤器的执行流程 使用过滤器 route过滤器的默认三种配置 路由到服务 路由到url地址 转发给自己 自定义过滤器 简介 Zuul是Netflix开源的微服务网关&#xff0c;主要功能是路由转发和过滤器&#xff0c;其原理也是一系列filters&#xff0…...

为什么要有分布式锁?

Redis避坑指南&#xff1a;为什么要有分布式锁&#xff1f;作者&#xff1a;京东保险 张江涛1、为什么要有分布式锁&#xff1f;JUC提供的锁机制&#xff0c;可以保证在同一个JVM进程中同一时刻只有一个线程执行操作逻辑&#xff1b;多服务多节点的情况下&#xff0c;就意味着有…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...