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

链表学习基础

链表

通过指针串联在一起的线性结构,每个节点由数据域指针域两部分组成。链表节点在内存中的存储通常不是连续的,各节点通过指针连接在一起,其内存分布大致如下图所示。

链表3

定义

单链表

struct ListNode {// DATATYPE 可以是任意存放数据的类型,如int, string等DATATYPE val; ListNode *next;ListNode(DATATYPE v) : val(v), next(nullptr) {}
};

链表1

双链表

双链表节点定义比单链表节点多一个指向前驱节点的指针域。

struct ListNode {DATATYPE val;ListNode *prev;ListNode *next;ListNode(DATATYPE v) : val(v), prev(nullptr), next(nullptr) {}
};

链表2

删除

在单链表中,删除一个节点,需要将该节点的前驱元素的 next 指针指向,该节点的后继元素。如果删除节点为头节点,则仅需找到正确的头节点即可。

链表-删除节点

插入

在单链表中,插入与删除相反,但仍需要找到插入的位置。将插入节点的 next 指针指向插入位置的后继节点,将插入位置的前驱节点指向插入节点。如果是头节点,则仅需要将插入节点指向原来头节点,将头节点标记为当前插入节点。

链表-添加节点

总结

链表在插入和删除上的时间复杂度为 O(1),在查询上的时间复杂度为 O(n)。

适用于数据量不固定,频繁增删,少量查询的场景。

解题技巧

  • 额外的数据结构(哈希表);
  • 快慢指针;
  • 虚拟头节点;

面试&笔试

在面试和笔试中,对算法的要求应有所区分。

在笔试中,题量多时间少,我们要尽量采取写出容易想到并且时间复杂度符合要求的算法,通常可以以空间换时间。

而在面试中的题,通常难度更小,为了给面试官留下深刻的影响,应尽量写出低时间复杂度,低空间复杂度,能体现代码水平的代码。

Reference

通常难度更小,为了给面试官留下深刻的影响,应尽量写出低时间复杂度,低空间复杂度,能体现代码水平的代码。

Reference

  1. 代码随想录 (programmercarl.com)

相关文章:

链表学习基础

链表 通过指针串联在一起的线性结构,每个节点由数据域和指针域两部分组成。链表节点在内存中的存储通常不是连续的,各节点通过指针连接在一起,其内存分布大致如下图所示。 定义 单链表 struct ListNode {// DATATYPE 可以是任意存放数据的…...

springboot整合阿里云oss文件服务器

springboot整合阿里云oss文件服务器一、申请Bucket二、 获取AccessKey ID、AccessKey Secret三、 springboot整合3.1 在application.yml 配置参数3.2 oss需要的pom3.3 配置 oss配置类3.4 oss的controller类3.5 oss的service类以及impl一、申请Bucket 进入该网址对象存储oss述 …...

数据分析:旅游景点销售门票和消费情况分析

数据分析:旅游景点销售门票和消费情况分析 文章目录数据分析:旅游景点销售门票和消费情况分析一、前言二、数据准备三、分析数据四、用户购买门票数量分析五、用户复购分析六、用户回购分析七、占比分析1.每个月分层用户占比情况。2.每月不同用户的占比3…...

Android问题解决方案(一):Android 打空包后提示没有”android:exported“的属性设置

Android 打空包后提示没有”android:exported“的属性设置Android 打空包后提示没有”android:exported“的属性设置1、问题:2、文档3、参考链接:4、解决方案:Android 打空包后提示没有”android:exported“的属性设置 1、问题: …...

Portraiture2023最新版人像图像后期处理软件

2023全新发布Portraiture 4是专注于图像后期处理软件研发的 Imagenomic, LLC产品之一,在摄影爱好者中有点影响力。Portraiture可以将繁琐复杂的人像磨皮操作极致简化,不论是普通爱好者或专业后期处理人员,均能一键完成。凭借优秀的AI算法和多…...

链表OJ(七)删除有序链表中重复的元素-I -II

目录 删除有序链表中重复的元素-I 删除有序链表中重复的元素-II 删除有序链表中重复的元素-I 描述 删除给出链表中的重复元素(链表中元素从小到大有序),使链表中的所有元素都只出现一次 例如: 给出的链表为1→1→21→1→2,返回1…...

C语言经典编程题100例(81~100)

目录81、习题7-7 字符串替换82、习题8-10 输出学生成绩83、习题8-2 在数组中查找指定元素84、习题8-3 数组循环右移85、题8-9 分类统计各类字符个数86、习题9-2 计算两个复数之积87、习题9-6 按等级统计学生成绩88、习题11-1 输出月份英文名89、习题11-2 查找星期90、练习10-1 …...

ChIP-seq 分析:数据质控实操(5)

1. 数据 今天将继续回顾我们在上一次中研究的 Myc ChIPseq。这包括用于 MEL 和 Ch12 细胞系的 Myc ChIPseq 及其输入对照。 可在此处[1]找到 MEL 细胞系中 Myc ChIPseq 的信息和文件可在此处[2]找到 Ch12 细胞系中 Myc ChIPseq 的信息和文件可以在此处[3]找到 MEL 细胞系的输入…...

java黑马头条 day5自媒体文章审核 敏感词过滤算法DFA 集成RabbitMQ实现自动审核

自动审核流程介绍 做为内容类产品,内容安全非常重要,所以需要进行对自媒体用户发布的文章进行审核以后才能到app端展示给用户。2 WmNews 中status 代表自媒体文章的状态 status字段:0 草稿 1 待审核 2 审核失败 3 人工审核 4 人工审核通过 …...

python--matplotlib(1)

前言 Matplotlib画图工具的官网地址是 http://matplotlib.org/ Python环境下实现Matlab制图功能的第三方库,需要numpy库的支持,支持用户方便设计出二维、三维数据的图形显示。 正文 1.arange函数 arange函数需要三个参数,分别为起始点、终止…...

华为OD机试题 - 获取最大软件版本号(JavaScript)

最近更新的博客 华为OD机试题 - 任务总执行时长(JavaScript) 华为OD机试题 - 开放日活动(JavaScript) 华为OD机试 - 最近的点 | 备考思路,刷题要点,答疑 【新解法】 华为OD机试题 - 最小步骤数(JavaScript) 华为OD机试题 - 任务混部(JavaScript) 华为OD机试题 - N 进…...

字符函数和字符串函数

字符串以\0为结束标志&#xff0c;strlen函数返回的是’\0’前的字符个数&#xff0c;不包括\0参数的指向的字符串必须是\0为结束标志&#xff0c;不然结果不确定函数的返回类型是size_t(无符号的整型&#xff09;strlen的使用#include <stdio.h> #include <string.h&…...

【猜名次】-C语言-题解

1. 描述&#xff1a; 5位运动员参加了10米台跳水比赛&#xff0c;有人让他们预测比赛结果&#xff1a; A选手说&#xff1a;B第二&#xff0c;我第三&#xff1b; B选手说&#xff1a;我第二&#xff0c;E第四&#xff1b; C选手说&#xff1a;我第一&#xff0c;D第二&#x…...

对 equals() 和 hashCode() 的理解?

在 java.lang.Object 类中有两个非常重要的方法&#xff1a; public native int hashCode(); public boolean equals(Object obj) {return (this obj); }Object 类是类继承结构的基础&#xff0c;是每一个类的父类&#xff0c;都实现了Object 类中定义的方法。 equals()方法…...

IDEA插件安装慢、超时、不成功问题如何解决?

目录 一、打开国内插件的节点IP地址 二、修改本地hosts文件 三、刷新DNS缓存 一、打开国内插件的节点IP地址 国内插件的节点IP地址查询: http://tool.chinaz.com/speedtest/plugins.jetbrains.com 在下方的检测结果中&#xff0c;找到一个解析时间最短的IP地址&#xff0c;解…...

软考高级之信息系统案例分析七重奏-《5》

五十、项目需求管理可能存在的问题。 1、未制定项目需求管理计划; 2、项目沟通存在问题; 3、项目经理缺乏必要的项目管理经验; 4、没有有效地管理需求变更控制; 5、没有有效地维护对需求进行跟踪管理; 6、没有按照规范的需求开发和需求管理的内容和流程开展需求工作…...

JUC并发编程 Ⅳ -- 共享模型之无锁

文章目录CAS 与 volatile问题引入代码分析volatile为什么无锁效率高CAS特点原子整数原子引用ABA 问题及解决原子数组原子(字段)更新器原子累加器UnsafeUnsafe CAS 操作管程即 monitor 是阻塞式的悲观锁实现并发控制&#xff0c;本文我们将通过非阻塞式的乐观锁的来实现并发控制…...

Spring之AOP实现

1. AOP的实现方式 使用AspectJ的编译器来改动class类文件实现增强(使用不广泛) ----- 编译阶段 这种对class类文件增强的, 也可以增强static静态方法, 而通过代理方式就无法实现静态方法的增强 可通过查看编译后class文件反编译后的java代码验证 agent增强(使用不广泛) ----- 类…...

Spring之基于xml的自动装配、基于Autowired注解的自动装配

文章目录基于xml的自动装配①注解②扫描③新建Maven Module④创建Spring配置文件⑤标识组件的常用注解⑥创建组件⑦扫描组件⑧测试⑨组件所对应的bean的id基于注解的自动装配①场景模拟②Autowired注解③Autowired注解其他细节④Autowired工作流程Autowire 注解的原理Qualifier…...

【案例】--(非分布式)轻量级任务调度平台

目录 一、前言说明二、背景2.1、完成任务,顺便搭建了一个任务调度平台三、具体实现解析3.1、技术栈等选型3.2、完成具体功能解析(1)、支持基本任务功能(2)、支持日志收集功能(3)、支持用户异常,选择性关闭调度功能(4)、实时监控正在执行和任务队列的任务情况(5)、实时监控任务…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...