[LeetCode]day10 707.设计链表

707. 设计链表 - 力扣(LeetCode)

题目描述

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

单链表中的节点应该具备两个属性: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 

解题

我们创建一个虚拟头结点,使操作更简便一些。

class MyLinkedList {public:
//定义结点
struct linkNode{int val;linkNode*next;linkNode(int val):val(val),next(nullptr){}
};MyLinkedList() {this->size=0;this->head=new linkNode(0); //创建一个虚拟头结点}int get(int index) {if(index<0||index>=size){return -1;}//从有效结点开始遍历!linkNode*p=head->next;for(int i=0;i<index;i++){p=p->next;}return p->val;}void addAtHead(int val) {linkNode*newNode=new linkNode(val);newNode->next=head->next;head->next=newNode;size++;}void addAtTail(int val) {linkNode*p=head;while(p->next){p=p->next;}linkNode*newNode=new linkNode(val);p->next=newNode;size++;}void addAtIndex(int index, int val) {if (index > size) {return;}linkNode*p=head;for(int i=0;i<index;i++){p=p->next;}//遍历到前一个结点linkNode*newNode=new linkNode(val);newNode->next=p->next;p->next=newNode;size++;}void deleteAtIndex(int index) {if (index < 0 || index >= size) {return;}size--;linkNode*p=head;//遍历到前一个结点for(int i=0;i<index;i++){p=p->next;}linkNode*nodeTode=p->next;p->next=p->next->next;delete nodeTode;}
private:
int size; //真实结点数
linkNode* head;
};/*** 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);*/

易错点在于遍历时初始化linkNode*p 时 要初始化为头结点 即linkeNode*p=head;不能默认初始化为空

加了一个虚拟头结点之后相当于链表中实际上有size+1个结点 所以每次for循环如果是从head节点开始,都是遍历到第index个结点前的一个结点 而我们get函数中需要遍历到第index个结点 所以从第一个有效结点head->next开始!

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

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

相关文章

动态规划DP 背包问题 完全背包问题(题目分析+C++完整代码)

概览检索 动态规划DP 概览&#xff08;点击链接跳转&#xff09; 动态规划DP 背包问题 概览&#xff08;点击链接跳转&#xff09; 完全背包问题 原题链接 AcWiing 3. 完全背包问题 题目描述 有 N种物品和一个容量是 V的背包&#xff0c;每种物品都有无限件可用。 第 i种物…

开源智慧园区管理系统对比五款主流产品探索智能运营新模式

内容概要 在这个数字化迅速发展的时代&#xff0c;园区管理也迎来了全新的机遇和挑战。众所周知&#xff0c;开源智慧园区管理系统作为一种创新解决方案&#xff0c;正逐步打破传统管理的局限性。它的开放性不仅使得系统可以根据具体需求进行灵活调整&#xff0c;也为用户提供…

Unity实现按键设置功能代码

一、前言 最近在学习unity2D&#xff0c;想做一个横版过关游戏&#xff0c;需要按键设置功能&#xff0c;让用户可以自定义方向键与攻击键等。 自己写了一个&#xff0c;总结如下。 二、界面效果图 这个是一个csv文件&#xff0c;准备第一列是中文按键说明&#xff0c;第二列…

稀疏混合专家架构语言模型(MoE)

注&#xff1a;本文为 “稀疏混合专家架构语言模型&#xff08;MoE&#xff09;” 相关文章合辑。 手把手教你&#xff0c;从零开始实现一个稀疏混合专家架构语言模型&#xff08;MoE&#xff09; 机器之心 2024年02月11日 12:21 河南 选自huggingface 机器之心编译 机器之心…

C++哈希(链地址法)(二)详解

文章目录 1.开放地址法1.1key不能取模的问题1.1.1将字符串转为整型1.1.2将日期类转为整型 2.哈希函数2.1乘法散列法&#xff08;了解&#xff09;2.2全域散列法&#xff08;了解&#xff09; 3.处理哈希冲突3.1线性探测&#xff08;挨着找&#xff09;3.2二次探测&#xff08;跳…

29.Word:公司本财年的年度报告【13】

目录 NO1.2.3.4 NO5.6.7​ NO8.9.10​ NO1.2.3.4 另存为F12&#xff1a;考生文件夹&#xff1a;Word.docx选中绿色标记的标题文本→样式对话框→单击右键→点击样式对话框→单击右键→修改→所有脚本→颜色/字体/名称→边框&#xff1a;0.5磅、黑色、单线条&#xff1a;点…

深入理解Java引用传递

先看一段代码&#xff1a; public static void add(String a) {a "new";System.out.println("add: " a); // 输出内容&#xff1a;add: new}public static void main(String[] args) {String a null;add(a);System.out.println("main: " a);…

Python从零构建macOS状态栏应用(仿ollama)并集成AI同款流式聊天 API 服务(含打包为独立应用)

在本教程中,我们将一步步构建一个 macOS 状态栏应用程序,并集成一个 Flask 服务器,提供流式响应的 API 服务。 如果你手中正好持有一台 MacBook Pro,又怀揣着搭建 AI 聊天服务的想法,却不知从何处迈出第一步,那么这篇文章绝对是你的及时雨。 最终,我们将实现以下功能: …

Qt之数据库操作三

主要介绍qt框架中对数据库的增加&#xff0c;删除和修改功能。 软件界面如下 程序结构 tdialogdata.h中代码 #ifndef TDIALOGDATA_H #define TDIALOGDATA_H#include <QDialog> #include<QSqlRecord> namespace Ui { class TDialogData; }class TDialogData : pub…

neo4j入门

文章目录 neo4j版本说明部署安装Mac部署docker部署 neo4j web工具使用数据结构图数据库VS关系数据库 neo4j neo4j官网Neo4j是用ava实现的开源NoSQL图数据库。Neo4作为图数据库中的代表产品&#xff0c;已经在众多的行业项目中进行了应用&#xff0c;如&#xff1a;网络管理&am…

JVM-运行时数据区

JVM的组成 运行时数据区-总览 Java虚拟机在运行Java程序过程中管理的内存区域&#xff0c;称之为运行时数据区。 《Java虚拟机规范》中规定了每一部分的作用 运行时数据区-应用场景 Java的内存分成哪几部分&#xff1f; Java内存中哪些部分会内存溢出&#xff1f; JDK7 和J…

Java篇之继承

目录 一. 继承 1. 为什么需要继承 2. 继承的概念 3. 继承的语法 4. 访问父类成员 4.1 子类中访问父类的成员变量 4.2 子类中访问父类的成员方法 5. super关键字 6. super和this关键字 7. 子类构造方法 8. 代码块的执行顺序 9. protected访问修饰限定符 10. 继承方式…

leetcode——验证二叉搜索树(java)

给你一个二叉树的根节点 root &#xff0c;判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下&#xff1a; 节点的左子树只包含小于当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 示例 1&#xff1a; 输入…

家居EDI:Hom Furniture EDI需求分析

HOM Furniture 是一家成立于1977年的美国家具零售商&#xff0c;总部位于明尼苏达州。公司致力于提供高品质、时尚的家具和家居用品&#xff0c;满足各种家庭和办公需求。HOM Furniture 以广泛的产品线和优质的客户服务在市场上赢得了良好的口碑。公司经营的产品包括卧室、客厅…

Spring Boot + Facade Pattern : 通过统一接口简化多模块业务

文章目录 Pre概述在编程中&#xff0c;外观模式是如何工作的&#xff1f;外观设计模式 UML 类图外观类和子系统的关系优点案例外观模式在复杂业务中的应用实战运用1. 项目搭建与基础配置2. 构建子系统组件航班服务酒店服务旅游套餐服务 3. 创建外观类4. 在 Controller 中使用外…

八、Spring Boot 日志详解

目录 一、日志的用途 二、日志使用 2.1 打印日志 2.1.1 在程序中获取日志对象 2.1.2 使用日志对象打印日志 2.2、日志框架介绍 2.2.1 门面模式(外观模式) 2.2.2 门面模式的实现 2.2.3 SLF4J 框架介绍 2.3 日志格式的说明 2.4 日志级别 2.4.1 日志级别的分类 2.4.2…

创建前端项目的方法

目录 一、创建前端项目的方法 1.前提&#xff1a;安装Vue CLI 2.方式一&#xff1a;vue create项目名称 3.方式二&#xff1a;vue ui 二、Vue项目结构 三、修改Vue项目端口号的方法 一、创建前端项目的方法 1.前提&#xff1a;安装Vue CLI npm i vue/cli -g 2.方式一&…

(leetcode 213 打家劫舍ii)

代码随想录&#xff1a; 将一个线性数组换成两个线性数组&#xff08;去掉头&#xff0c;去掉尾&#xff09; 分别求两个线性数组的最大值 最后求这两个数组的最大值 代码随想录视频 #include<iostream> #include<vector> #include<algorithm> //nums:2,…

【Python】第七弹---Python基础进阶:深入字典操作与文件处理技巧

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】【C详解】【Linux系统编程】【MySQL】【Python】 目录 1、字典 1.1、字典是什么 1.2、创建字典 1.3、查找 key 1.4、新增/修改元素 1.5、删除元素 1.6、遍历…

本地部署DeepSeek开源多模态大模型Janus-Pro-7B实操

本地部署DeepSeek开源多模态大模型Janus-Pro-7B实操 Janus-Pro-7B介绍 Janus-Pro-7B 是由 DeepSeek 开发的多模态 AI 模型&#xff0c;它在理解和生成方面取得了显著的进步。这意味着它不仅可以处理文本&#xff0c;还可以处理图像等其他模态的信息。 模型主要特点:Permalink…