链表OJ经典题目及思路总结(一)
目录
- 前言
- 1.移除元素
- 1.1 链表
- 1.2 数组
- 2.双指针
- 2.1 找链表的中间结点
- 2.2 找倒数第k个结点
- 总结
前言
解代码题
先整体:首先数据结构链表的题一定要多画图,捋清问题的解决思路;
后局部:接着考虑每一步具体如何实现,框架搭好后,处理坑点,考虑细枝末节,通常要考虑以下几个容易出错的点
需要单独处理的头结点、尾结点
越界问题
头指针为NULL
循环继续、结束条件等
而思路这一块,有的思路好想,但是无论从时间复杂度还是空间复杂度上来看,可能不是优良的算法。但有一些比较清奇的思路,见得题多了,反思总结,也就收入囊中啦!比如下面介绍的双指针,以及翻转数组的思路都很优秀。
每个小节开头蓝色字体是题目链接,大家可以先做一下题~
1.移除元素
1.1 链表
203.移除链表元素(题目链接)
思路1:遍历链表,删除数据域为val的结点;
思路2:将值不为val的节点尾插到新的链表中,返回新链表的头结点(头指针)。
注意:两种思路整体都是遍历原链表,但是有几个坑!
坑点1
:如果尾插第一个结点,要更改新的头指针newhead;但后续插入不需要再更改头指针。坑点2
:如果最后一个结点的值不是val,那么将其尾插到新链表,其next指针域为NULL;但是如果最后一个结点的值是val,其前一个结点(假设prev指向该结点)被尾插到新链表,prev->next指向的最后一个节点(数据域为val)被free,那么prev->next是野指针,所以要将其置为NULL.
比如下图中当数据域为5的结点被尾插到新链表之后,tail指向该节点,tail->next=p,但是free§之后,p就是野指针了,应将tail->next手动置为NULL.
坑点3
:第二点和链表本身为空可以合在一起考虑,如果head为NULL,那么cur为NULL,遍历原链表的while循环不会执行,tail为NULL,newhead为NULL,直接返回即可;而如果tail不为NULL,tail->next有可能为NULL,不考虑太多,直接置为NULL.
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* cur=head, *newhead=NULL, *tail=NULL;//cur用于遍历要删除的链表//newhead用于存放要新链表的头指针,用于返回//tail用于尾插,否则每次尾插都要遍历新链表找尾节点,效率不高while(cur)//while循环遍历要删除的链表{//结点数据域为val与非val分开处理,val则删除,非val则尾插到新链表if(cur->val!=val){//插入第一个元素和后续元素不同的是,插入第一个元素需要更改头指针,要单独处理//坑点1 if(tail==NULL)newhead=tail=cur;else{tail->next=cur;tail=tail->next;}cur=cur->next;}else{struct ListNode* next=cur->next;free(cur);cur=next;}}//坑点2,3if(tail)tail->next=NULL;return newhead;
}
1.2 数组
27.移除元素(题目链接)
这个题的思路可以是,创建一个新的数组存储值不为val的数组元素。
也可以使用双指针,数组的指针就是下标,使用src指针遍历数组,如果值不为val,就将其赋值到nums[dst++].
int removeElement(int* nums, int numsSize, int val) {int src=0,dst=0;while(src<numsSize){if(nums[src]!=val)nums[dst++]=nums[src++];//只有当值非val的时候,存储到数组中,以dst为指针,也就是舍弃值为val的元素elsesrc++;//每次循环src都++,达到遍历数组的目的}return dst;
}
2.双指针
2.1 找链表的中间结点
876.链表的中间结点(题目链接)
考虑快慢指针,fast, slow指针刚开始均指向第一个结点,接着fast每次走两步,slow每次走一步;如果是奇数结点,fast->next为NULL时,slow指向中间结点;如果是偶数结点,fast为NULL时,slow指向两个中间结点的第二个结点。也即fast遍历链表,当fast为NULL或fast->next为NULL时停止循环,返回slow.
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* middleNode(struct ListNode* head) {struct ListNode* fast=head,*slow=head;while(fast && fast->next){fast=fast->next->next;slow=slow->next;}return slow;
}
这个思路和下面这道题有点像!
2.2 找倒数第k个结点
02.返回倒数第k个节点(题目链接)
思路:考虑双指针,fast走到NULL终止循环,那么此时fast相当于倒数第0个结点,slow是倒数第k个结点,也即fast比slow多走了k步,那么让fast先走k步,接着fast和slow同步往前走,直到fast为NULL.
代码如下
(如果fast走到最后一个节点停止,那么考虑fast先走k-1步)
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
int kthToLast(struct ListNode* head, int k){struct ListNode* fast=head,*slow=head;while(k--){if(fast==NULL)return NULL;//考虑链表本身为空的情况fast=fast->next;}while(fast){fast=fast->next;slow=slow->next;}return slow->val;
}
总结
链表代码题考虑时间复杂度、空间复杂度,同时要多见题,多见经典题,多练,总结经典思路,以及常见坑点,写代码时考虑细枝末节。细节考虑不到位,可能存在提交不通过,对未通过测试用例的提示进行分析,调试,提升自身解决问题的能力。
相关文章:

链表OJ经典题目及思路总结(一)
目录 前言1.移除元素1.1 链表1.2 数组 2.双指针2.1 找链表的中间结点2.2 找倒数第k个结点 总结 前言 解代码题 先整体:首先数据结构链表的题一定要多画图,捋清问题的解决思路; 后局部:接着考虑每一步具体如何实现,框架…...

初识chatgpt
GPT到底是什么 首先,我们需要了解GPT的全称:Generative Pre-trained Transformer,即三个关键词:生成式 预训练 变换模型。 (1)什么是生成式? 即能够生成新的文本序列。 (2&#…...
【60天备战2024年11月软考高级系统架构设计师——第33天:云计算与大数据架构——大数据处理框架的应用场景】
随着大数据技术的发展,越来越多的企业开始采用大数据处理框架来解决实际问题。理解这些框架的应用场景对于架构师来说至关重要。 大数据处理框架的应用场景 实时数据分析:使用Apache Kafka与Apache Spark结合,可以实现对实时数据流的处理与…...

如何设计具体项目的数据库管理
### 例三:足协的数据库管理算法 #### 角色: - **ESFP学生**:小明 - **ENTP老师**:张老师 #### 主题:足协的数据库管理算法 --- **张老师**:小明,今天我们来讨论一下足协的数据库管理算法。你…...

对于 Vue CLI 项目如何引入Echarts以及动态获取数据
🚀个人主页:一颗小谷粒 🚀所属专栏:Web前端开发 很荣幸您能阅读我的文章,诚请评论指点,欢迎欢迎 ~ 目录 1、数据画卷—Echarts介绍 1.1 什么是Echarts? 1.2 Echarts官网地址 2、Vue CLI 项目…...

【Linux笔记】在VMware中,为基于NAT模式运行的CentOS虚拟机设置固定的网络IP地址
一、配置VMware虚拟网络 1、打开VMware虚拟网络编辑器: 点击VMware主界面上方的“编辑”菜单,选择“虚拟网络编辑器”。 2、选择NAT模式网络: 在虚拟网络编辑器中,选择VMnet8(或其他NAT模式的网络)。 取消勾…...

一文上手Kafka【中】
一、发送消息细节 在发送消息的特别注意: 在版本 3.0 中,以前返回 ListenableFuture 的方法已更改为返回 CompletableFuture。为了便于迁移,2.9 版本添加了一个方法 usingCompletableFuture(),该方法为 CompletableFu…...
Ubuntu如何如何安装tcpdump
在Ubuntu上安装tcpdump非常简单,可以通过以下步骤完成: 打开终端。 更新包列表: 首先,更新你的包管理器的包列表: sudo apt update 安装tcpdump: 使用以下命令安装tcpdump: sudo apt install …...

3-3 AUTOSAR RTE 对SR Port的作用
返回总目录->返回总目录<- 一、前言 RTE作为SWC和BSW之间的通信机构,支持Sender-Receiver方式实现ECU内及ECU间的通信。 对于Sender-Receiver Port支持三种模式: 显式访问:若运行实体采用显示模式的S/R通信方式,数据读写是即时的;隐式访问:当多个运行实体需要读取…...
hive/impala/mysql几种数据库的sql常用写法和函数说明
做大数据开发的时候,会在几种库中来回跳,同一个需求,不同库函数和写法会有出入,在此做汇总沉淀。 1. hive 1. 日期差 DATEDIFF(CURRENT_DATE(),wdjv.creation_date) < 30 30天内的数据 2.impala 3. spark 4. mysql 1.时间差…...
论文阅读:LM-Cocktail: Resilient Tuning of Language Models via Model Merging
论文链接 代码链接 Abstract 预训练的语言模型不断进行微调,以更好地支持下游应用。然而,此操作可能会导致目标领域之外的通用任务的性能显著下降。为了克服这个问题,我们提出了LM Cocktail,它使微调后的模型在总体上保持弹性。我们的方法以模型合并(Model Merging)的形…...

8640 希尔(shell)排序
### 思路 希尔排序是一种基于插入排序的排序算法,通过将待排序数组分割成多个子序列分别进行插入排序来提高效率。初始增量d为n/2,之后每次减半,直到d为1。 ### 伪代码 1. 读取输入的待排序关键字个数n。 2. 读取n个待排序关键字并存储在数组…...

Linux 安装redis主从模式+哨兵模式3台节点
下载 https://download.redis.io/releases/ 解压 tar -zxvf redis-7.2.4.tar.gz -C /opt chmod 777 -R /opt/redis-7.2.4/安装 # 编译 make # 安装, 一定是大写PREFIX make PREFIX/opt/redis-7.2.4/redis/ install配置为系统服务 cd /etc/systemd/system/主服务…...
[BCSP-X2024.小高3] 学习计划
题目描述 暑假共有 n 天,第 i 天的精力指数为 a[i],你想要利用假期依次(按 1,2,...,m 顺序)复习 m 门功课,第 i 门功课的重要程度为 b[i],且每门的复习时段必须连 续,并且不能有某天不干事。 …...
Android Debug Bridge(ADB)完全指南
文章目录 前言一、什么是ADB?二、ADB的工作原理ADB由三个部分组成: 三、如何安装ADBWindows系统:macOS和Linux系统: 四、ADB常用指令大全设备相关操作1. 查看连接的设备:2. 重启设备:3. 进入Bootloader模式…...
再次重逢,愿遍地繁花
再次重逢,愿遍地繁花 我并不是一个对最终幻想7很热衷的粉丝,也并没有像那些评论区的大佬,能够轻易地说出整部世界的全貌。说到底,我只是一个看完了《最终幻想7:重制版》和《最终幻想7:重生》的爱好者罢了。…...
数据结构和算法基础(一)
文章目录 链表反转链表合并删除链表倒数第 n 个结点找链表的中间结点链表中环的检测排序算法递归 趁空闲时间刷一遍极客时间上王争的《数据结构与算法之美》课程,个人觉得写的很好,每章节由浅入深且从基础到引入设计类问题,如果写过很多代码想…...

【超长好文】网络安全从业者面试指南
文章为笔者偶然看到的github项目《网络安全面试指南》,作者FeeiCN,读完内容深感作者的用心,尽管一些观点因为时间原因与当下行情存在差异,但仍旧值得大家参考,希望能给大家在这行业寒冬带来一些启发,愿正在…...

基于大数据的高校新生数据可视化分析系统
作者:计算机学姐 开发技术:SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等,“文末源码”。 专栏推荐:前后端分离项目源码、SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码 精品专栏:…...

【cache】浅析四种常用的缓存淘汰算法 FIFO/LRU/LFU/W-TinyLFU
本文浅析淘汰策略与工作中结合使用、选取,并非针对算法本身如何实现的 文章目录 FIFOLFULRUW-TinyLFU实践与优化监控与调整 FIFO first input first output , 先进先出,即最早存入的元素最先取出, 典型数据结构代表:…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘
美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...

如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...

【Oracle】分区表
个人主页:Guiat 归属专栏:Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

AI病理诊断七剑下天山,医疗未来触手可及
一、病理诊断困局:刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断",医生需通过显微镜观察组织切片,在细胞迷宫中捕捉癌变信号。某省病理质控报告显示,基层医院误诊率达12%-15%,专家会诊…...

网站指纹识别
网站指纹识别 网站的最基本组成:服务器(操作系统)、中间件(web容器)、脚本语言、数据厍 为什么要了解这些?举个例子:发现了一个文件读取漏洞,我们需要读/etc/passwd,如…...

免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...