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

链表OJ经典题目及思路总结(一)

目录

  • 前言
  • 1.移除元素
    • 1.1 链表
    • 1.2 数组
  • 2.双指针
    • 2.1 找链表的中间结点
    • 2.2 找倒数第k个结点
  • 总结

前言

解代码题
先整体:首先数据结构链表的题一定要多画图,捋清问题的解决思路;
后局部:接着考虑每一步具体如何实现,框架搭好后,处理坑点,考虑细枝末节,通常要考虑以下几个容易出错的点

  1. 需要单独处理的头结点、尾结点
  2. 越界问题
  3. 头指针为NULL
  4. 循环继续、结束条件等

而思路这一块,有的思路好想,但是无论从时间复杂度还是空间复杂度上来看,可能不是优良的算法。但有一些比较清奇的思路,见得题多了,反思总结,也就收入囊中啦!比如下面介绍的双指针,以及翻转数组的思路都很优秀。

每个小节开头蓝色字体是题目链接,大家可以先做一下题~


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个结点 总结 前言 解代码题 先整体&#xff1a;首先数据结构链表的题一定要多画图&#xff0c;捋清问题的解决思路&#xff1b; 后局部&#xff1a;接着考虑每一步具体如何实现&#xff0c;框架…...

初识chatgpt

GPT到底是什么 首先&#xff0c;我们需要了解GPT的全称&#xff1a;Generative Pre-trained Transformer&#xff0c;即三个关键词&#xff1a;生成式 预训练 变换模型。 &#xff08;1&#xff09;什么是生成式&#xff1f; 即能够生成新的文本序列。 &#xff08;2&#…...

【60天备战2024年11月软考高级系统架构设计师——第33天:云计算与大数据架构——大数据处理框架的应用场景】

随着大数据技术的发展&#xff0c;越来越多的企业开始采用大数据处理框架来解决实际问题。理解这些框架的应用场景对于架构师来说至关重要。 大数据处理框架的应用场景 实时数据分析&#xff1a;使用Apache Kafka与Apache Spark结合&#xff0c;可以实现对实时数据流的处理与…...

如何设计具体项目的数据库管理

### 例三&#xff1a;足协的数据库管理算法 #### 角色&#xff1a; - **ESFP学生**&#xff1a;小明 - **ENTP老师**&#xff1a;张老师 #### 主题&#xff1a;足协的数据库管理算法 --- **张老师**&#xff1a;小明&#xff0c;今天我们来讨论一下足协的数据库管理算法。你…...

对于 Vue CLI 项目如何引入Echarts以及动态获取数据

&#x1f680;个人主页&#xff1a;一颗小谷粒 &#x1f680;所属专栏&#xff1a;Web前端开发 很荣幸您能阅读我的文章&#xff0c;诚请评论指点&#xff0c;欢迎欢迎 ~ 目录 1、数据画卷—Echarts介绍 1.1 什么是Echarts&#xff1f; 1.2 Echarts官网地址 2、Vue CLI 项目…...

【Linux笔记】在VMware中,为基于NAT模式运行的CentOS虚拟机设置固定的网络IP地址

一、配置VMware虚拟网络 1、打开VMware虚拟网络编辑器&#xff1a; 点击VMware主界面上方的“编辑”菜单&#xff0c;选择“虚拟网络编辑器”。 2、选择NAT模式网络&#xff1a; 在虚拟网络编辑器中&#xff0c;选择VMnet8&#xff08;或其他NAT模式的网络&#xff09;。 取消勾…...

一文上手Kafka【中】

一、发送消息细节 在发送消息的特别注意: 在版本 3.0 中&#xff0c;以前返回 ListenableFuture 的方法已更改为返回 CompletableFuture。为了便于迁移&#xff0c;2.9 版本添加了一个方法 usingCompletableFuture&#xff08;&#xff09;&#xff0c;该方法为 CompletableFu…...

Ubuntu如何如何安装tcpdump

在Ubuntu上安装tcpdump非常简单&#xff0c;可以通过以下步骤完成&#xff1a; 打开终端。 更新包列表&#xff1a; 首先&#xff0c;更新你的包管理器的包列表&#xff1a; sudo apt update 安装tcpdump&#xff1a; 使用以下命令安装tcpdump&#xff1a; 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常用写法和函数说明

做大数据开发的时候&#xff0c;会在几种库中来回跳&#xff0c;同一个需求&#xff0c;不同库函数和写法会有出入&#xff0c;在此做汇总沉淀。 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)排序

### 思路 希尔排序是一种基于插入排序的排序算法&#xff0c;通过将待排序数组分割成多个子序列分别进行插入排序来提高效率。初始增量d为n/2&#xff0c;之后每次减半&#xff0c;直到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 # 安装&#xff0c; 一定是大写PREFIX make PREFIX/opt/redis-7.2.4/redis/ install配置为系统服务 cd /etc/systemd/system/主服务…...

[BCSP-X2024.小高3] 学习计划

题目描述 暑假共有 n 天&#xff0c;第 i 天的精力指数为 a[i]&#xff0c;你想要利用假期依次&#xff08;按 1,2,...,m 顺序&#xff09;复习 m 门功课&#xff0c;第 i 门功课的重要程度为 b[i]&#xff0c;且每门的复习时段必须连 续&#xff0c;并且不能有某天不干事。 …...

Android Debug Bridge(ADB)完全指南

文章目录 前言一、什么是ADB&#xff1f;二、ADB的工作原理ADB由三个部分组成&#xff1a; 三、如何安装ADBWindows系统&#xff1a;macOS和Linux系统&#xff1a; 四、ADB常用指令大全设备相关操作1. 查看连接的设备&#xff1a;2. 重启设备&#xff1a;3. 进入Bootloader模式…...

再次重逢,愿遍地繁花

再次重逢&#xff0c;愿遍地繁花 我并不是一个对最终幻想7很热衷的粉丝&#xff0c;也并没有像那些评论区的大佬&#xff0c;能够轻易地说出整部世界的全貌。说到底&#xff0c;我只是一个看完了《最终幻想7&#xff1a;重制版》和《最终幻想7&#xff1a;重生》的爱好者罢了。…...

数据结构和算法基础(一)

文章目录 链表反转链表合并删除链表倒数第 n 个结点找链表的中间结点链表中环的检测排序算法递归 趁空闲时间刷一遍极客时间上王争的《数据结构与算法之美》课程&#xff0c;个人觉得写的很好&#xff0c;每章节由浅入深且从基础到引入设计类问题&#xff0c;如果写过很多代码想…...

【超长好文】网络安全从业者面试指南

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

基于大数据的高校新生数据可视化分析系统

作者&#xff1a;计算机学姐 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等&#xff0c;“文末源码”。 专栏推荐&#xff1a;前后端分离项目源码、SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码 精品专栏&#xff1a;…...

【cache】浅析四种常用的缓存淘汰算法 FIFO/LRU/LFU/W-TinyLFU

本文浅析淘汰策略与工作中结合使用、选取&#xff0c;并非针对算法本身如何实现的 文章目录 FIFOLFULRUW-TinyLFU实践与优化监控与调整 FIFO first input first output &#xff0c; 先进先出&#xff0c;即最早存入的元素最先取出&#xff0c; 典型数据结构代表&#xff1a;…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

如何将联系人从 iPhone 转移到 Android

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

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;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病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

网站指纹识别

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

免费PDF转图片工具

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