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

LeetCode 707. 设计链表(单链表、(非循环)双链表 模板)

你可以选择使用单链表或者双链表,设计并实现自己的链表。

单链表中的节点应该具备两个属性:val 和 next 。val 是当前节点的值,next 是指向下一个节点的指针/引用。

如果是双向链表,则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类:

  • MyLinkedList() 初始化 MyLinkedList 对象。
  • int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效,则返回 -1 。
  • void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后,新节点会成为链表的第一个节点。
  • void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
  • void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度,那么该节点会被追加到链表的末尾。如果 index 比长度更大,该节点将 不会插入 到链表中。
  • void deleteAtIndex(int index) 如果下标有效,则删除链表中下标为 index 的节点。

示例:

输入
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]解释
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
myLinkedList.get(1);              // 返回 2
myLinkedList.deleteAtIndex(1);    // 现在,链表变为 1->3
myLinkedList.get(1);              // 返回 3

提示:

  • 0 <= index, val <= 1000
  • 请不要使用内置的 LinkedList 库。
  • 调用 getaddAtHeadaddAtTailaddAtIndex 和 deleteAtIndex 的次数不超过 2000 。

解题思路:

都在代码里

(什么时候加this什么时候不加? 感觉刷题的时候好像不用考虑权限修饰符和this)

代码如下:

单链表:

class ListNode { // 单链表结点定义int val;ListNode next;ListNode() {}ListNode(int val) {this.val = val;}
}class MyLinkedList {int size; // size存储链表元素的个数ListNode head; // 虚拟头结点public MyLinkedList() { // 初始化链表size = 0;head = new ListNode(0);}public int get(int index) { // 获取第index个结点的数值,index从0开始,第0个结点就是头结点if(index < 0 || index >= size) return -1;ListNode cur = head; // 新建一个结点指针,初始指向头结点for(int i = 0; i <= index; i++) { // index从0开始,第0个结点是头结点cur = cur.next; // 指针cur不断向后移动,直到指向了第index个结点}return cur.val;}public void addAtHead(int val) { // 先实现addAtIndex,头插就相当于在第0个结点前添加addAtIndex(0, val);}public void addAtTail(int val) { // 先实现addAtIndex,尾插就相当于在第(size)个结点前添加addAtIndex(size, val);}public void addAtIndex(int index, int val) { // 在第index个结点前插入一个新结点if(index > size) return;if(index < 0) index = 0;size++;ListNode pre = head; // 找到要插入结点的前驱结点for(int i = 0; i < index; i++) {pre = pre.next;}ListNode newNode = new ListNode(val); // 插入该结点newNode.next = pre.next;pre.next = newNode;}public void deleteAtIndex(int index) {if(index < 0 || index >= size) return ;size--;if(index == 0) {head = head.next;return;}ListNode pre = head;for(int i = 0; i < index; i++) {pre = pre.next;}pre.next = pre.next.next;}
}/*** Your MyLinkedList object will be instantiated and called as such:* MyLinkedList obj = new MyLinkedList();* int param_1 = obj.get(index);* obj.addAtHead(val);* obj.addAtTail(val);* obj.addAtIndex(index,val);* obj.deleteAtIndex(index);*/

双链表:
 

class ListNode { // 双链表结点定义int val;ListNode pre;ListNode next;ListNode() {}ListNode(int val) {this.val = val;}
}class MyLinkedList {int size; // 双链表长度ListNode head; //设置一个头指针指向虚拟头结点ListNode tail; //设置一个尾指针指向最后一个结点public MyLinkedList() { // 初始化size = 0;head = new ListNode(0);tail = new ListNode(0);// 关键:初始时要把头尾结点先连起来,即对头结点和尾结点的指针进行初始化head.pre = null;head.next = tail;tail.pre = head;tail.next = null;}public int get(int index) {if(index < 0 || index >= size) return -1;ListNode cur = head;if(index >= size / 2) { // 判断从哪边开始遍历时间更短cur = tail; // 从尾结点开始往前for(int i = size - 1; i >= index; i--) {cur = cur.pre;}} else {for(int i = 0; i <= index; i++) {cur = cur.next;}}return cur.val;}public void addAtHead(int val) {addAtIndex(0, val);}public void addAtTail(int val) {addAtIndex(size, val);}public void addAtIndex(int index, int val) {if(index > size) return;if(index < 0) index = 0;size++;ListNode prePointer = head;for(int i = 0; i < index; i++) { //找到待插入结点的前一个结点prePointer = prePointer.next;}ListNode newNode = new ListNode(val);newNode.next = prePointer.next;prePointer.next.pre = newNode;newNode.pre = prePointer;prePointer.next = newNode;}public void deleteAtIndex(int index) {if(index < 0 || index >= size) return;size--;ListNode prePointer = head;for(int i = 0; i < index; i++) {prePointer = prePointer.next;}prePointer.next.next.pre = prePointer;prePointer.next = prePointer.next.next;}
}/*** Your MyLinkedList object will be instantiated and called as such:* MyLinkedList obj = new MyLinkedList();* int param_1 = obj.get(index);* obj.addAtHead(val);* obj.addAtTail(val);* obj.addAtIndex(index,val);* obj.deleteAtIndex(index);*/

相关文章:

LeetCode 707. 设计链表(单链表、(非循环)双链表 模板)

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

深入了解Flutter中Overlay的介绍以及使用

Flutter Overlay 介绍 在 Flutter 中&#xff0c;Overlay 是一种特殊的 Widget&#xff0c;它可以用来在应用程序的其他部分之上显示内容。Overlay 非常适合用于显示模态对话框、弹出菜单、工具提示等。 Overlay 的工作原理 Overlay 位于 Flutter 的渲染树之外&#xff0c;这…...

文本直接生成2分钟视频,即将开源模型StreamingT2V

Picsart人工智能研究所、德克萨斯大学和SHI实验室的研究人员联合推出了StreamingT2V视频模型。通过文本就能直接生成2分钟、1分钟等不同时间&#xff0c;动作一致、连贯、没有卡顿的高质量视频。 虽然StreamingT2V在视频质量、多元化等还无法与Sora媲美&#xff0c;但在高速运…...

时序预测 | Matlab实现SOM-BP自组织映射结合BP神经网络时间序列预测

时序预测 | Matlab实现SOM-BP自组织映射结合BP神经网络时间序列预测 目录 时序预测 | Matlab实现SOM-BP自组织映射结合BP神经网络时间序列预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 1.Matlab实现SOM-BP自组织映射结合BP神经网络时间序列预测&#xff08;完整源码…...

FPGA高端图像处理开发板-->鲲叔4EV:12G-SDI、4K HDMI2.0、MIPI等接口谁敢与我争锋?

目录 前言鲲叔4EV----高端FPGA图像处理开发板核心板描述底板描述配套例程源码描述配套服务描述开发板测试视频演示开发板获取 前言 在CSDN写博客传播FPGA开发经验已经一年多了&#xff0c;帮助了不少人&#xff0c;也得罪了不少人&#xff0c;有的人用我的代码赢得了某些比赛、…...

linux练习-交互式传参

在shell脚本中&#xff0c;read 向用户显示一行文本并接受用户输入 #!/bin/bash read -p 依次输入你的姓名、年龄、家乡 name age home echo 我是$name,年龄$age,我来自$home...

【数据结构(一)】初识数据结构

❣博主主页: 33的博客❣ ▶文章专栏分类: Java从入门到精通◀ &#x1f69a;我的代码仓库: 33的代码仓库&#x1f69a; &#x1faf5;&#x1faf5;&#x1faf5;关注我带你学更多数据结构知识 目录 1.前言2.集合架构3.时间和空间复杂度3.1算法效率3.2时间复杂度3.2.1大O的渐进…...

前端三剑客 —— CSS (第六节)

目录 内容回顾&#xff1a; 弹性布局属性介绍 案例演示 商品案例 布局分析 登录案例 网格布局 内容回顾&#xff1a; 变量&#xff1a;定义变量使用 --名称&#xff1a;值&#xff1b; 使用变量&#xff1a; 属性名&#xff1a;var&#xff08;--名称&#xff09;&a…...

MyBatis 解决上篇的参数绑定问题以及XML方式交互

前言 上文:MyBatis 初识简单操作-CSDN博客 上篇文章我们谈到的Spring中如何使用注解对Mysql进行交互 但是我们发现我们返回出来的数据明显有问题 我们发现后面三个字段的信息明显没有展示出来 下面我们来谈谈解决方案 解决方案 这里的原因本质上是因为mysql中和对象中的字段属性…...

Rust语言之属性宏(Attribute Macro)derive

文章目录 Rust语言之属性宏&#xff08;Attribute Macro&#xff09;derive Rust语言之属性宏&#xff08;Attribute Macro&#xff09;derive 属性宏是一种基于属性的宏&#xff0c;用于修改、扩展或注解 Rust 代码。它们通常用于为函数、结构体、枚举、模块等添加元数据或自…...

[技术闲聊]我对电路设计的理解(六)-原理图封装

电路设计的直观体现就是完整的原理图&#xff0c;绘制电路图阶段的第一步&#xff0c;绘制原理图封装库。 封装库一共有两种&#xff0c;一种是原理图封装库&#xff0c;一种是PCB封装库&#xff0c;如下图所示。 原理图封装和PCB封装之间的唯一关联就是 引脚位号&#xff0c;…...

算法(滑动窗口四)

1.串联所有单词的子串 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。 s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。 例如&#xff0c;如果 words ["ab","cd","ef"]&#xff…...

学习记录:bazel和cmake运行终端指令

Bazel和CMake都是用于构建软件项目的工具&#xff0c;但它们之间有一些重要的区别和特点&#xff1a; Bazel&#xff1a; Bazel是由Google开发的构建和测试工具&#xff0c;用于构建大规模的软件项目。它采用一种称为“基于规则”的构建系统&#xff0c;它利用构建规则和依赖关…...

蓝桥杯刷题--python-37-分解质因数

3491. 完全平方数 - AcWing题库 nint(input()) res1 i2 while i*i<n: if n%i0: t0 while n%i0: n//i t1 if t%2: res*i i1 if n>1: res*n print(res) 4658. 质因数个数 - AcWing题库…...

Delphi编写的图片查看器

UNIT Unit17;INTERFACEUSESWinapi.Windows, Winapi.Messages, System.SysUtils, System.Variants,System.Classes, Vcl.Graphics, Vcl.Controls, Vcl.Forms, Vcl.Dialogs,Vcl.StdCtrls, Vcl.ExtDlgs, Vcl.ExtCtrls, Vcl.Imaging.jpeg; //注意&#xff1a;要加入jpej 否侧浏览图…...

Swing中的FlowLayout/WrapLayout在打横排列时候如何做到置顶对齐

前言 最近在开发swing客户端时候碰到一个棘手的问题&#xff1a; Swing中的FlowLayout/WrapLayout在打横排列时候如何做到置顶对齐如果是vue或者react&#xff0c;一搜百度什么都出来了&#xff0c;swing的话&#xff0c;嗯。。。资料有点少而且大部分是stack overflow上面的…...

C# MES通信从入门到精通(8)——C#调用Webservice服务进行数据交互

前言 在上位机开发领域,使用webservice来访问客户的终端Mes系统是一项必备的技能,本文详细介绍了如何在c#中调用webservice服务,不仅介绍了使用添加服务引用直接调用webservice中的方法外还介绍了使用http的post方法调用webservice方法,过程详细且均为实战经验总结,对于初…...

day04-MQ

1.初识MQ 1.1.同步和异步通讯 微服务间通讯有同步和异步两种方式&#xff1a; 同步通讯&#xff1a;就像打电话&#xff0c;需要实时响应。异步通讯&#xff1a;就像发邮件&#xff0c;不需要马上回复。 两种方式各有优劣&#xff0c;打电话可以立即得到响应&#xff0c;但是你…...

神经网络汇聚层

文章目录 最大汇聚层平均汇聚层自适应平均池化层 最大汇聚层 汇聚窗口从输入张量的左上角开始&#xff0c;从左往右、从上往下的在输入张量内滑动。在汇聚窗口到达的每个位置&#xff0c;它计算该窗口中输入子张量的最大值或平均值。计算最大值或平均值是取决于使用了最大汇聚…...

2024.3.8力扣每日一题——找出美丽数组的最小和

2024.3.8 题目来源我的题解方法一 数学 题目来源 力扣每日一题&#xff1b;题序&#xff1a;2834 我的题解 方法一 数学 经过分析&#xff0c;在target之前&#xff0c;取小于等于target/2的正整数才能使得和最小&#xff0c;并且满足条件3。 时间复杂度&#xff1a;O(n) 空…...

单例模式以及线程安全问题

单例模式的概念 单例模式是指的是整个系统生命周期内&#xff0c;保证一个类只能产生一个实例对象 保证类的唯一性 。 通过一些编码上的技巧&#xff0c;使编译器可以自动发现咱们的代码中是否有多个实例&#xff0c;并且在尝试创建多个实例的时候&#xff0c;直接编译出错。 …...

车载电子电器架构 —— 软件下载

车载电子电器架构 —— 软件下载 我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 屏蔽力是信息过载时代一个人的特殊竞争力,任何消耗你的人和事,多看一眼都是你的不对。非必要不费力证明自己,无…...

阿里云弹性计算通用算力型u1实例性能评测,性价比高

阿里云服务器u1是通用算力型云服务器&#xff0c;CPU采用2.5 GHz主频的Intel(R) Xeon(R) Platinum处理器&#xff0c;ECS通用算力型u1云服务器不适用于游戏和高频交易等需要极致性能的应用场景及对业务性能一致性有强诉求的应用场景(比如业务HA场景主备机需要性能一致)&#xf…...

Jupyter IPython帮助文档及其魔法命令

1.IPython 的帮助文档 使用 help() 使用 ? 使用 &#xff1f;&#xff1f; tab 自动补全 shift tab 查看参数和函数说明 2.运行外部 Python 文件 使用下面命令运行外部 Python 文件&#xff08;默认是当前目录&#xff0c;也可以使用绝对路径&#xff09; %run *.py …...

设计模式总结-面向对象设计原则

面向对象设计原则 面向对象设计原则简介单一职责原则单一职责原则定义单一职责原则分析单一职责原则实例 开闭原则开闭原则定义开闭原则分析开闭原则实例 里氏代换原则里氏代换原则定义里氏代换原则分析 依赖倒转原则依赖倒转原则定义依赖倒转原则分析依赖倒转原则实例 接口隔离…...

绿联 安装zfile,创建属于自己的网盘,支持直链分享

绿联 安装zfile&#xff0c;创建属于自己的网盘&#xff0c;支持直链分享 1、镜像 zhaojun1998/zfile:latest ZFile ZFile 是一个适用于个人的在线网盘(列目录)程序&#xff0c;可以将你各个存储类型的存储源&#xff0c;统一到一个网页中查看、预览、维护&#xff0c;再也不用…...

KnowLog:基于知识增强的日志预训练语言模型|顶会ICSE 2024论文

徐波 东华大学副教授 东华大学计算机学院信息技术系副系主任&#xff0c;复旦大学知识工场实验室副主任&#xff0c;智能运维方向负责人。入选“上海市青年科技英才扬帆计划”。研究成果发表在IJCAI、ICDE、ICSE、ISSRE、ICWS、CIKM、COLING等国际会议上&#xff0c;曾获中国数…...

前端:用Sass简化媒体查询

在进行媒体查询的编写的时候&#xff0c;我们可以利用scss与与编译器&#xff0c;通过include混入的方式对代码进行简化&#xff0c;从而大大提高了代码的可维护性&#xff0c;也减少了代码的编写量&#xff0c;废话不多说&#xff0c;直接上代码 // 定义设备数值 $breakpoints…...

如何快速写出漂亮的Button按钮呢?

你是否曾在浏览网页时&#xff0c;被那些色彩鲜艳、功能多样的按钮所吸引&#xff1f;无论是提交表单&#xff0c;还是触发一个动作&#xff0c;按钮都扮演着不可或缺的角色。今天聊聊网页设计中的 <button> 标签。 1. 基础语法 什么是 <button> 标签 <butto…...

美摄科技AI智能图像矫正解决方案

图像已经成为了企业传播信息、展示产品的重要媒介&#xff0c;在日常拍摄过程中&#xff0c;由于摄影技巧的限制和拍摄环境的复杂多变&#xff0c;许多企业面临着图像内容倾斜、构图效果不佳等挑战&#xff0c;这无疑给企业的形象展示和信息传递带来了不小的困扰。 美摄科技深…...

网站开发与spark/江阴百度推广公司

2021考研数学大纲变动笔记 前言 变动如下 参考&#xff1a;2021考研数学大纲变动一览表 题型结构&#xff1a; 题型2020大纲2021大纲单选4*8325*1050填空4*6245*630解答题10*511 *49410*415 *270 内容调整&#xff1a; 高数线代概论2020大纲56%22%22%2021大纲60%20%20% 数…...

国内做网站的公司有哪些/青岛百度整站优化服务

随笔 推迟了一周才发布这篇文章实属罪过&#xff0c;最近延迟更新是因为最近在研究下一个系列“微服务、云原生”文章的整体排版。不得不吐糟一句&#xff0c;java的内容真的是多到没边&#xff0c;尤其是当微服务成为主流&#xff0c;导致程序员之间的层级化也越来越严重&…...

seo管理系统易语言/应用宝aso优化

2019独角兽企业重金招聘Python工程师标准>>> Apache服务器80端口被占用——解决方法 80端口被占用解决办法有两种&#xff1a; 1.关闭占用80端口的程序&#xff0c;这时Apache服务器会正常启动&#xff1b; 2.修改Apache的端口&#xff0c;比如改为8081&#xff1b;…...

如何做网站赚钱/如何免费做视频二维码永久

git 忽略 IntelliJ .idea文件 2016年10月22日 11:31:27 阅读数&#xff1a;6196 标签&#xff1a; git 更多 个人分类&#xff1a; git版权声明&#xff1a;本文为博主原创文章&#xff0c;未经博主允许不得转载。 https://blog.csdn.net/zhuzhupozhuzhuxia/article/details/52…...

做公司网站需要准备什么资料/信息流优化师招聘

刚好在学习 PHP 反序列化&#xff0c;听说有这么个后门&#xff0c;尝试着分析下&#xff0c;可能有写的不对的地方&#xff0c;还请指教。首先介绍下序列化与反序列化。序列化是对象串行化&#xff0c;对象是一种在内存中存储的数据类型&#xff0c;寿命随生成该对象的程序的终…...

网站专业建设/百度收录入口在哪里查询

1确保服务器端数据库服务已经启动 开始->所有程序->Microsoft SQL Server 2008->Configutation Tools&#xff0c;打开SQL Server Configuration Manager&#xff0c;点击SQL Server Services&#xff0c;查看数据库服务是否已经启动&#xff0c;如果服务未开启&#…...