【数据结构】链表相关题目(简单版)

🚀write in front🚀
📜所属专栏: 初阶数据结构
🛰️博客主页:睿睿的博客主页
🛰️代码仓库:🎉VS2022_C语言仓库
🎡您的点赞、关注、收藏、评论,是对我最大的激励和支持!!!
关注我,关注我,关注我,你们将会看到更多的优质内容!!

文章目录
- 前言
- 习题1:
- 习题2
- 习题3
- 衍生题1:
- 衍生题2:
- 习题4:
- 习题5:
- 总结
前言
在学完了顺序表的基本知识后,我们可以通过一些习题来巩固所学知识!
习题1:
删除链表中等于给定值 val 的所有结点。oj链接

这道题目有两种做法:
- 方法一:双指针的遍历,通过双指针来查找删除节点并连接后面的节点,但是缺点就是会有特殊情况需要考虑(头删的情况),代码如下:

- 方法2:通过遍历,将节点尾插到新链表,最后返回新链表,代码如下:
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode*cur=head,*newnode=NULL,*tail=NULL;while(cur){if(cur->val!=val){if(newnode==NULL){newnode=cur;tail=cur;}else{tail->next=cur;tail=tail->next;}cur=cur->next;}else{struct ListNode*next=cur;cur=next->next;free(next);}}
if(tail)
{tail->next=NULL;
}return newnode;
}
习题2
反转一个单链表。oj链接

这道题也有两种方法,
- 方法1:用三指针的方法,前两个来改变每个节点的链接关系,最后一个节点用来标记位置方便遍历链表

代码如下:

- 方法2:取每个节点头插到新链表:

习题3
给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。oj链接

这里我们就要介绍一下快慢指针了。通过快慢指针我们可以解决很多问题,以后都会用到。
那么什么是快慢指针呢?
顾名思义,快慢指针就是通过两个不同指针步长的不同来遍历链表。

这道题我们让一个指针走两步,一个指针走一步,当快指针指向空或快指针的next指向空的时候,慢指针指向位置就是中间节点位置。
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode*slow=head,*fast=head;while(fast!=NULL&&fast->next!=NULL){slow=slow->next;fast=fast->next->next;}return slow;
}
衍生题1:
输入一个链表,输出该链表中倒数第k个结点。oj链接

其实也是快慢指针的思想,只是这里不是步长的不同,而是起点不同:
要寻找倒数第k个节点,就让快指针的起点在慢指针的后k步。当快指针指向空的时候,慢指针就指向倒数第k个节点。
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {// write code herestruct ListNode* slow=pListHead;struct ListNode* fast=pListHead;while(k--){if(fast==NULL){return NULL;}fast=fast->next;}while(fast){fast=fast->next;slow=slow->next;}return slow;
}
衍生题2:
给定一个链表,判断链表中是否有环。oj链接

这道题也是用快慢指针,即慢指针一次走一步,快指针一次走两步,两个指针从链表起始位置开始运行,如果链表带环则一定会在环中相遇,否则快指针率先走到链表的末尾。比如:陪女朋友到操作跑步减肥。
那么,为什么快指针每次走两步,慢指针走一步可以?
假设链表带环,两个指针最后都会进入环,快指针先进环,慢指针后进环。
此时,两个指针每移动一次,之间的距离就缩小一步,不会出现每次刚好是套圈的情况,因此:在满指针走到一圈之前,快指针肯定是可以追上慢指针的,即相遇。
代码如下:
bool hasCycle(struct ListNode *head)
{struct ListNode*fast=head,*slow=head;if(head==NULL||head->next==NULL){return false;}fast=fast->next;while(fast!=slow){if(fast==NULL||fast->next==NULL)break;fast=fast->next->next;slow=slow->next;}if(fast==slow)return true;return false;
}
习题4:
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的oj链表
这道题引入了哨兵位,也就是空的头节点。其实,对于链表尾插的时候,需要判断是否为空,比较麻烦,只要我们创建一个空的头节点就可以避免很多情况。
链表在头插的时候我们不需要头节点;
链表在尾插的有空的头节点会更方便。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{struct ListNode*newnode=(struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode*tail=newnode;tail->next=NULL;while(list1&&list2){if(list1->val<list2->val){tail->next=list1;tail=list1;list1=list1->next;}else{tail->next=list2;tail=list2;list2=list2->next;}}if(list1)tail->next=list1;
if(list2)tail->next=list2;return newnode->next;
}
习题5:
编写代码,以给定值x为基准将链表分割成两部分,所有小于x的结点排在大于或等于x的结点之前 。oj链接

这道题我们创建两个新链表(带有哨兵位的空头节点),小于的尾插到一个链表,大于的尾插到另外一个链表,最后将他们连起来即可。
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code herestruct ListNode*greaternode=NULL;struct ListNode*lessnode=NULL,*cur=pHead;struct ListNode* gtail=greaternode,*ltail=lessnode;while(cur!=NULL){if(cur->val>=x){gtail->next=cur;gtail=cur;cur=cur->next;gtail->next=NULL;}else{ltail->next=cur;ltail=cur;cur=cur->next;ltail->next=NULL;}}ltail->next=greaternode->next;return lessnode->next;}
};
总结
还是那句话,数据结构需要多画图,并且对各种情况要有十足的把握才能做对题目。
更新不易,辛苦各位小伙伴们动动小手,👍三连走一走💕💕 ~ ~ ~ 你们真的对我很重要!最后,本文仍有许多不足之处,欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正!
专栏订阅:
每日一题
c语言学习
算法
智力题
初阶数据结构
更新不易,辛苦各位小伙伴们动动小手,👍三连走一走💕💕 ~ ~ ~ 你们真的对我很重要!最后,本文仍有许多不足之处,欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正!

相关文章:
【数据结构】链表相关题目(简单版)
🚀write in front🚀 📜所属专栏: 初阶数据结构 🛰️博客主页:睿睿的博客主页 🛰️代码仓库:🎉VS2022_C语言仓库 🎡您的点赞、关注、收藏、评论,是…...
通信原理 | FFT/STFT 你真的学会了吗?
文章目录 原理FFT的例子1必须要理解的点函数FFT返回值的数据结构具有对称性单边谱和双边谱变换后到频域后的横坐标和纵坐标是什么?FFT的例子2FFT的例子3短时傅里叶变换(STFT)原理 傅里叶告诉我们,现实中的任和信号波形都可以视为一系列正弦信号的叠加。 那对于一个给定的信…...
Qt使用API实现鼠标点击操作
前段时间,工作需要进行数据录入,每次都要点击3次按钮,想让鼠标自行点击,只要下位机接入,就自动点击按钮把数据读出,录入到服务端,并且进行检测,说干就干,没有经验,那只有面向百度编程. 根据查到的资料,可以使用WinAPI进行鼠标模似.可以使用的函数有两个,一个是SendMessageA(),…...
JavaWeb学习-Tomcat
常用的Web服务器 ①IIS:Microsoft的Web服务器产品为Internet Information Services (IIS),IIS 是允许在公共Intranet或Internet上发布信息的Web服务器。ⅡS是目前最流行的Web服务器产品之一,很多著名的网站都是建立在…...
【蓝牙系列】蓝牙5.4到底更新了什么(2)
【蓝牙系列】蓝牙5.4到底更新了什么(2) 一、 背景 上一篇文章讲了蓝牙5.4的PAwR特征,非常适合应用在电子货架标签(ESL)领域, 但是实际应用场景中看,只有PAwR特性是不够的,如何保证广…...
js中window自带的四舍五入toFixed方法中的坑以及解决办法
Hello,各位,我胡汉三~啊呸,我又回来啦,还改了名,换了头像,哈哈哈!时隔这么长时间不更新了,太忙了,平时笔记都记在了自己的电脑上,从今天起,继续更…...
JeecgBoot 3.5.0 版本发布,开源的企业级低代码平台
项目介绍 JeecgBoot是一款企业级的低代码平台!前后端分离架构 SpringBoot2.x,SpringCloud,Ant Design&Vue3,Mybatis-plus,Shiro,JWT 支持微服务。强大的代码生成器让前后端代码一键生成! JeecgBoot引领…...
行测-判断推理-图形推理-样式规律-空间重构-四面体和八面体
B很明显就是对的,可以看到就选B走人A选项:横线的右边应该是菱形,而不是竖线,排除AC选项:菱形的左边应该是横线,而不是竖线,排除CD选项:横线脚底下踩的应该是三角形砖,而不…...
HTML5新特性
HTML5 简介 HTML5 是下一代 HTML 标准。 HTML5在HTML4.01的基础上新增了一些特性,从而可以让我们能够更快捷更方便的开发应用,同时去掉了一些 “糟粕”。 现在的主流浏览器基本都支持HTML5。 在一个HTML5 文档中的第一行,我们需要使用<…...
TDengine Schemaless(无模式写入)常见问题的原因及故障排除
Tips:使用版本:3.0.2.6 (一)TDengine ERROR (80003002): Invalid data format 格式化问题;如缺少必要的组成格式(时间戳、超级表等),或有字符串未作修饰符修饰,类似的还…...
【前端八股文】浏览器系列:浏览器渲染、前端路由、前端缓存(HTTP缓存)、缓存存储(HTTP缓存存储、本地存储)
文章目录渲染步骤DOM树与render树回流与重绘前端路由hash模式history模式两种模式对比前端缓存HTTP缓存强缓存协商缓存一般哪些文件对应哪些缓存HTTP缓存总结缓存存储HTTP缓存存储本地存储参考本系列目录:【前端八股文】目录总结 是以《代码随想录》八股文为主的笔记…...
SpiderFlow爬虫获取网页节点
SpiderFlow爬虫获取网页节点 一、SpiderFlow 文档地址:https://www.spiderflow.org/ 二、问题:获取一篇文章的标题、来源、发布时间、正文、下载附件该怎么获取? 举例:【公示】第三批智能光伏试点示范名单公示 三、抓取网页步骤…...
“微服务架构:优点、缺点及实现方式“
微服务是一种软件开发架构,它将应用程序拆分成小型、独立的服务单元。每个服务单元都是自给自足的,它们可以独立地进行开发、测试和部署。这种架构的好处是它可以使软件更容易维护、扩展和更新,同时还可以提高开发团队的灵活性和效率。在本文…...
c/c++实现crc码计算和校验
算法介绍 循环冗余校验(Cyclic Redundancy Check, CRC)是一种根据网络数据包或计算机文件等数据产生简短固定位数校验码的一种信道编码技术,主要用来检测或校验数据传输或者保存后可能出现的错误。它是利用除法及余数的原理来作错…...
漏洞分析丨cve20110104
作者丨黑蛋目标程序调试工具16进制编辑器XP SP3office 2003ollydbg010Editor三、漏洞验证首先我们配置环境,并下载poc:使用ollydbg附加office excel 2003:打开poc可以看到发生了访问违规异常,像地址0x51453844中写入时发生异常&am…...
关于vue-router路径配置的问题(此文主要是记录三级路由的访问路径,以及安装、路由组件、路由重定向)
一、路由的定义node路由:用户根据不同的url地址,来访问不同的页面vue路由(客户端):组件结合路由规则来构建单页面应用二、下载安装npm ——>终端输入npm i vue-router3 -S ——>回车 (3为版本的意思&…...
SpringBoot 整合 clickhouse和mysql 手把手教程全网最详细
最近做一个项目 需要 整合mysql clickhouse 多数据源 后台用的是ruoyi框架 1. 首先pom引入相关依赖 <!--JDBC-clickhouse数据库--><dependency><groupId>com.clickhouse</groupId><artifactId>clickhouse-jdbc</artifactId><version&…...
Leetcode-java 数据结构回顾 Day01
数据结构复习 虽说是复习,但是都差不多忘干净了。而且用c做题做的多。 借从Leetcode上做题的机会,记一记自己之前学过的java知识。 链表 数组好歹写个动态规划,还能对六七十个样例,链表是一点头绪都没,尤其是要写头…...
Java spring cloud 企业工程管理系统源码+项目模块功能清单
工程项目各模块及其功能点清单 一、系统管理 1、数据字典:实现对数据字典标签的增删改查操作 2、编码管理:实现对系统编码的增删改查操作 3、用户管理:管理和查看用户角色 4、菜单管理:实现对系统菜单的增删改查操…...
用Biome-BGC模型如何模拟水循环过程
在Biome-BGC模型中,对于碳的生物量积累,采用光合酶促反应机理模型计算出每天的初级生产力(GPP),将生长呼吸和维持呼吸减去后的产物分配给叶、枝条、干和根。生物体的碳每天都按一定比例以凋落方式进入凋落物碳库;对于水份输运过程…...
QMK Toolbox:机械键盘固件定制与刷写全攻略
QMK Toolbox:机械键盘固件定制与刷写全攻略 【免费下载链接】qmk_toolbox A Toolbox companion for QMK Firmware 项目地址: https://gitcode.com/gh_mirrors/qm/qmk_toolbox 一、核心价值:重新定义键盘控制自由 QMK Toolbox 作为开源硬件领域的…...
The Leather Archive应用案例:从赛博都市到极简主义的皮衣穿搭
The Leather Archive应用案例:从赛博都市到极简主义的皮衣穿搭 1. 项目概述 「The Leather Archive」是一个基于AI技术的高端皮衣穿搭生成系统,它巧妙融合了Anything V5基础模型与Stable Yogi皮衣系列LoRA的专业能力。与传统AI工具不同,该项…...
PVB于EVA胶片的区别
PVB于EVA胶片的区别实例:PVB用于封装“双玻璃光伏组件”:玻璃+PVB+电池片+PVB+玻璃,PVB胶片已取代EVA胶片。为什么用PVB,不像我们现在一样用EVA?因为: 在玻璃…...
OpenClaw极简部署:nanobot镜像+手机Termux方案
OpenClaw极简部署:nanobot镜像手机Termux方案 1. 为什么要在手机上部署OpenClaw? 去年夏天,我在咖啡馆等朋友时突发奇想:如果能用手机随时调用AI助手处理文件该多好。当时尝试了几款云端AI工具,但要么功能受限&#…...
当NB-IoT遇上同步轨道卫星:GEO场景下的定时关系增强全指南(基于3GPP Release 17最新规范)
GEO卫星场景下NB-IoT定时关系增强技术解析 1. GEO卫星通信与NB-IoT的技术融合挑战 地球静止轨道(GEO)卫星通信与窄带物联网(NB-IoT)技术的结合,为全球物联网覆盖提供了革命性解决方案。GEO卫星位于地球赤道上空35,786公…...
旧Mac重生指南:用OpenCore Legacy Patcher解锁macOS新版本
旧Mac重生指南:用OpenCore Legacy Patcher解锁macOS新版本 【免费下载链接】OpenCore-Legacy-Patcher 体验与之前一样的macOS 项目地址: https://gitcode.com/GitHub_Trending/op/OpenCore-Legacy-Patcher 你是否有一台性能依然强劲却被苹果官方抛弃的旧Mac&…...
JavaScript动态交互:在网页中实时调整参数并预览LiuJuan生成效果
JavaScript动态交互:在网页中实时调整参数并预览LiuJuan生成效果 你是不是也遇到过这种情况?想用AI模型生成图片,但每次调整参数都要在代码里改来改去,然后重新运行脚本,等半天才能看到效果。整个过程就像在开盲盒&am…...
PasteMD真实案例分享:从零散笔记到结构化学习计划的全过程
PasteMD真实案例分享:从零散笔记到结构化学习计划的全过程 1. 引言:当杂乱笔记遇上智能格式化 你是否经历过这样的困境?电脑桌面上散落着十几个临时创建的记事本文件,手机备忘录里堆满了未经整理的零散想法,会议录音…...
UG/NX二次开发必备:C#和C++项目DLL自动签名与拷贝全攻略(附避坑指南)
UG/NX二次开发实战:C#与C项目DLL签名与部署全流程解析 在工业设计软件领域,Siemens NX(原Unigraphics)的二次开发能力一直是工程师扩展功能、提升效率的重要途径。而DLL文件的数字签名环节,则是确保开发成果能在正版NX…...
8_Harness驾驭工程实践:企业级落地与OpenAI案例解析
8_Harness驾驭工程实践:企业级落地与OpenAI案例解析 关键字: 企业级落地、OpenAI、Ryan Lopopolo、Codex、Harness Engineering、Citi Bank、Ancestry、Ulta Beauty、Agent-First开发、部署策略、自托管、成本优化、迁移路径、最佳实践、0行手写代码、百…...
