建设上线网站/网络营销是干嘛的
文章目录
- 前言
- 链表的中间结点
- 链表中倒数第k个结点
- 写在最后
前言
-
对于单链表的OJ练习,需要深刻理解做题的思路,这样我们才能够在任何场景都能够熟练的解答有关链表的问题。
-
关于OJ练习(1):-> 传送门 <-,其题目较为简单,思路也好理解,本章与
(1)
差不多,难度不大,核心点就在于理解解题思路。
链表的中间结点
题目链接:-> 传送门 <-。
- 该题目描述为:给你单链表的头结点 head ,请你找出并返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。
1.如果节点数为奇数,这个中间节点就显而易见了。(3)
2.如果节点数为偶数,这里认为中间两个节点的第二个节点为中间节点。(4)
思路一:
-
我们可以先遍历一遍链表,统计一下链表节点的个数。
-
然后将这个个数除以二加一(count / 2 + 1)便是中间这个节点的位置。
-
当然,我们在循环寻找这个中间节点的时候,是从头节点开始的,因此循环只需要循环
((count / 2 + 1) - 1)
即可。
代码实现:
struct ListNode* middleNode(struct ListNode* head){struct ListNode* cur = head;int count = 0;while (cur){count ++ ;cur = cur->next;}count = count / 2 + 1;while (-- count) // 循环count - 1次{head = head->next;}return head;
}
思路二:
-
该做法为快慢指针。
-
啥为快慢指针呢?在本题有关当中,我们定义两个指针指向链表的头节点,并且共同遍历链表,不同的是,一个指针每一次走两步,另一个指针每次走一步,这就是快慢指针。
-
每当快指针满足循环结束条件,慢指针都是指向链表的中间节点的。因为快指针走两步,慢指针走一步,整个移动的位移差相差一倍,所以每当快指针满足结束条件的时候,慢指针走的步数都是快指针走的步数的一半, 因此慢指针指向的那个节点就是整个链表的中间节点。
-
快指针结束的条件有两种情况,一种是快指针刚好指向空结束,一种是快指针指向尾节点结束,也就是快指针的
next
为NULL
。
1.当快指针刚好指向NULL
结束,此时链表的节点个数为偶数:
2.当快指针指向尾节点结束,也就是快指针的next
为NULL
,此时链表的节点个数为奇数:
代码实现:
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;
}
注意:
while
循环的判断条件,fast
一定要在前面,这是因为:判断是从左到右判断的,如果fast->next
在前,而此时链表的结点的个数为偶数,那么fast
就会直接到达NULL
,这时候对空指针解引用操作就出问题了。
链表中倒数第k个结点
题目链接:-> 传送门 <-。
- 该题目描述为:输入一个链表,输出该链表中倒数第k个结点。。
思路一:
-
既然是倒数第
k
个,那我们就看看是正数的第几个。 -
先遍历一遍单链表,统计一下链表的结点个数(
count
),通过数学知识,可得倒数的第k
个结点就是正数的第count - k + 1
个节点,这时只要在遍历一次链表,找到第count - k + 1
个节点返回即可。 -
当然,这里嘚注意
k
是不是大于链表节点的个数的情况。
代码实现:
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {struct ListNode* cur = pListHead;int count = 0;// 统计链表节点的个数while (cur){count ++ ;cur = cur->next;}// 如果k大于链表的节点个数,直接返回NULLif (k > count) return NULL;int tmp = count - k;// 由于从头个节点开始算,因此只需要循环count - k次就可以找到倒数第k个节点while (tmp -- ){pListHead = pListHead->next;}return pListHead;
}
思路二:
- 同样是快慢指针,这里的快慢指针解法是:快指针先向后走
k
步或者先向后走k - 1
步,然后快指针与慢指针同时向后走,当快指针满足循环结束条件停止,此时慢指针指向的节点就是倒数第k
个节点。
1.如果快指针先向后走k
步,此时快指针与慢指针之间相差k
步,因此,当快指针到达NULL
时,此时慢指针刚好指向倒数第k
个节点。(倒数第k
个节点与NULL
相差k
步)(循环结束条件:fast == NULL
)
2.如果快指针先向后走k - 1
步,此时快指针与慢指针之间相差k - 1
步,然后快指针与慢指针同时向后走,当快指针满足循环结束条件停止,此时慢指针指向的节点就是倒数第k
个节点。(倒数第k
个节点与尾节点
相差k - 1
步)(循环结束条件:fast->next == NULL
)
代码实现:(这里只实现fast先走k步的情况,fast先走k - 1的情况大同小异)
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {struct ListNode* slow = pListHead, * fast = pListHead;// fast先走k步while (k -- ){if (!fast) return NULL; // 如果k还没为0但fast已经指向空了,说明k大于链表的结点的个数,此时直接返回NULLfast = fast->next;}// 当fast为NULL时结束循环while (fast){fast = fast->next;slow = slow->next;}return slow;
}
写在最后
对于单链表的题目练习,最重要的是思路,我们在数据结构阶段要养成画图的习惯,因为它能帮助我们更好的理解。后续还会有单链表相关的题目练习。
感谢阅读本小白的博客,错误的地方请严厉指出噢!
相关文章:

【基础算法】单链表的OJ练习(2) # 链表的中间结点 # 链表中倒数第k个结点 #
文章目录前言链表的中间结点链表中倒数第k个结点写在最后前言 对于单链表的OJ练习,需要深刻理解做题的思路,这样我们才能够在任何场景都能够熟练的解答有关链表的问题。 关于OJ练习(1):-> 传送门 <-,…...

vue路由文件拆分管理
随着项目的原来越大,路由越来越多,我们的路由也会越来越多,如果都集中在一个文件中,会很冗杂文件很长。这时候我们可以将路由文件拆分,可读、方便管理。多人合作添加路由也能更多的避免代码冲突 代码拆分目录如图&…...

实例解析Java反射
反射是大多数语言里都必不不可少的组成部分,对象可以通过反射获取他的类,类可以通过反射拿到所有方法(包括私有),拿到的方法可以调用,总之通过“反射”,我们可以将Java这种静态语言附加上动态特…...

Android 9适配经验总结
目录四大组件适配Activity启动方式适配Service启动方式适配前台服务需要添加权限限制静态广播的接收限制ContentResolver数据更新操作权限与安全相关主要适配点运行时动态权限申请默认不支持 http 请求SharedPreferences 适配四大组件适配 Android 应用的开发离不开 Android 四…...

定时任务调度方案——Xxl-Job
定时任务调度方案 随着系统规模的发展,项目的组织结构以及架构越来越复杂,业务覆盖的范围越来越广,定时任务数量日益增多,任务也变得越来越复杂,尤其是为了满足在用户体量日历增大时,系统能够稳定运行&…...

操作系统引导
操作系统是一种程序,程序以数据的形式存放在硬盘中,而硬盘通常分为多个区,一个计算机中又有多个或多种外部设备。 操作系统引导指的是计算机利用CPU运行特定程序,通过程序识别硬盘,识别硬盘分区,识别硬盘分…...

[C#] 多线程单例子,分为阻塞型和分阻塞型, 在unity里的应用
在单例中使用多线程时,需要注意以下几点: 线程安全:在多线程环境下,单例对象可能被多个线程同时访问,因此需要确保单例的线程安全,避免出现数据竞争等问题。 对象创建:如果在单例对象的构造函数…...

使用MAT进行内存分析,并找到OOM问题
前言 在处理一次现场问题时,发现服务还在运行,但是出现假死情况,后通过分析GC日志以及使用MAT分析确定问题是内存溢出OutOfMemery(OOM);这里只记录MAT分析学习过程,最近工作忙,补记录。 GC日志分析 首先,如…...

初识Python
目录初识Python1.Python简介Python的优缺点Python的应用领域2.安装Python解释器Windows环境Linux环境macOS环境3.运行Python程序确认Python的版本编写Python源代码运行程序代码中的注释4.Python开发工具IDLE - 自带的集成开发工具IPython - 更好的交互式编程工具Sublime Text -…...

tmux终端复用软件
一、安装[rootpool-100-1-1-159 test]# yum install tmux [rootpool-100-1-1-159 test]# yum search tmux Repository extras is listed more than once in the configuration Last metadata expiration check: 0:33:52 ago on Fri 03 Mar 2023 09:10:34 AM CST.Name Exactly M…...

IO详解(文件,流对象,一些练习)
目录 文件 文件概念 文件的路径 路径有俩种表示风格 文件类型 如何区分文本文件还是二进制文件? java对文件的操作 File类中的一些方法 流对象 流对象的简单概念 java标准库的流对象 1.字节流,(操作二进制数据的) 2.字符流 (操作文本数据的) 流对象最核心的四个…...

SpringCloud全家桶— — 【1】eureka、ribbon、nacos、feign、gateway
SpringCloud全家桶— — 组件搭建 1 Eureka 1.1 Eureka-server 创建eureka-server的SpringBoot项目 ①导入依赖 <dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-starter-netflix-eureka-server</artifactId…...

【线程安全篇】
线程安全之原子性问题 x ,在字节码文件中对应多个指令,多个线程在运行多个指令时,就存在原子性、可见性问题 赋值 多线程场景下,一个指令如果包含多个字节码指令,那么就不再是原子操作。因为赋值的同时,…...

错误:EfficientDet网络出现“No boxes to NMS“并且mAP:0.0的解决方案
近日,在使用谷歌新推出来的一个网络EfficientDet进行目标检测训练自己的数据集的时候,出现了如下错误: 其中项目开源地址是:https://github.com/toandaominh1997/EfficientDet.Pytorch 上面截图中的1和2代表我的类别名称。读者可…...

python的opencv操作记录13——区域生长及分水岭算法
文章目录图像区域基本算法——形态学运算腐蚀与膨胀开运算与闭运算opencv中的形态学运算距离计算——distanceTransform函数连通域连通的定义计算连通域——connectedComponents连通域实验基于区域的分割区域生长算法自定义一个最简单区域生长算法实现区域分割一般区域分割open…...

一文看懂网上下单的手机流量卡为什么归属都是随机的!
最近很多网上下单的小伙伴们心中似乎都有一个疑问。那就是网上很多手机卡、流量卡都不能自选号码和归属地,就算能自选号码,归属地也是随机的而且很多都不会跟你说具体的城市,这是为什么呢?莫非其中有什么不可告人的秘密吗?小伙伴…...

python Pytest生成alluer测试报告的完整教程
1.下载allure包到本地,解压 网上很多资料,这边不提供了 2.配置环境变量 将上面解压后bin文件的路径复制,添加到环境变量Path下 3.验证环境变量配置是否功 在cmd中输入allure,回车 。查看allure是否成功: 4.pyc…...

4-spring篇
ApplicationContext refresh的流程 12个步骤 prepareRefresh 这一步创建和准备了Environment对象,并赋值给了ApplicationContext的成员变量 要理解Environment对象的作用 obtainFreshBeanFactory ApplicationContext 里面有一个成员变量,Beanfactory b…...

提升 Web 应用程序的性能:如何使用 JavaScript 编写缓存服务
缓存是一种重要的优化技术,用于加速数据访问和降低服务器负载。缓存存储经常访问的数据,以便在需要时可以快速检索。在本文中,我们将探索如何使用简单的数据结构在 JavaScript 中编写缓存服务。 编码缓存服务的第一步是定义将用于访问缓存的…...

供应商绩效管理指南:挑战、考核指标与管理工具
管理和优化供应商绩效既关键又具有挑战性。要知道价格并不是一切,如果你的供应商在商定的价格范围内向你开具发票,但服务达不到标准或货物不合格,你也无法达到节约成本的目标。 供应商绩效管理可以深入了解供应商可能带来的风险,…...

干货文稿|详解深度半监督学习
分享嘉宾 | 范越文稿整理 | William嘉宾介绍Introduction to Semi-Supervised Learning传统机器学习中的主流学习方法分为监督学习,无监督学习和半监督学习。这里存在一个是问题是为什么需要做半监督学习?首先是希望减少标注成本,因为目前可以…...

信箱|邮箱系统
技术:Java、JSP等摘要:在经济全球化和信息技术飞速发展的今天,通过邮件收发进行信息传递已经成为主流。目前,基于B/S(Browser/Server)模式的MIS(Management information system)日益…...

JS数组拓展
1、Array.from Array.from 方法用于将两类对象转为真正的数组: 类似数组的对象,所谓类似数组的对象,本质特征只有一点,即必须有length属性。 因此,任何有length属性的对象,都可以通过Array.from方法转为数组 和 可遍历…...

一道很考验数据结构与算法的功底的笔试题:用JAVA设计一个缓存结构
我在上周的笔试中遇到了这样一道题目,觉得有难度而且很考验数据结构与算法的功底,因此Mark一下。 需求说明 设计并实现一个缓存数据结构: 该数据结构具有以下功能: get(key) 如果指定的key存在于缓存中,则返回与该键关联的值&am…...

(10)C#传智:命名空间、String/StringBuilder、指针、继承New(第10天)
内容开始多了,慢品慢尝才有滋味。 一、命名空间namespace 用于解决类重名问题,可以看作类的文件夹. 若代码与被使用的类,与当前的namespace相同,则不需要using. 若namespace不同时,调用的方法:…...

基于Jetson Tx2 Nx的Qt、树莓派等ARM64架构的Ptorch及torchvision的安装
前提 已经安装好了python、pip及最基本的依赖库 若未安装好点击python及pip安装请参考这篇博文 https://blog.csdn.net/m0_51683386/article/details/129320492?spm1001.2014.3001.5502 特别提醒 一定要先根据自己板子情况,找好python、torch、torchvision的安…...

MySQL存储引擎详解及对比和选择
什么是存储引擎? MySQL中的数据用各种不同的技术存储在文件(或者内存)中。这些技术中的每一种技术都使用不同的存储机制、索引技巧、锁定水平并且最终提供广泛的不同的功能和能力。通过选择不同的技术,你能够获得额外的速度或者功能,从而改善…...

【推拉框-手风琴】vue3实现手风琴效果的组件
简言 在工作时有时会用到竖形手风琴效果的组件。 在此记录下实现代码和实现思路。 手风琴实现 结构搭建 搭建结构主要实现盒子间的排列效果。 用flex布局或者其他布局方式将内容在一行排列把每一项的内容和项头用盒子包裹, 内容就是这一项要展示的内容…...

滑动窗口最大值:单调队列
239. 滑动窗口最大值 难度困难2154收藏分享切换为英文接收动态反馈 给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 示例…...

负载均衡算法
静态负载均衡 轮询 将请求按顺序轮流地分配到每个节点上,不关心每个节点实际的连接数和当前的系统负载。 优点:简单高效,易于水平扩展,每个节点满足字面意义上的均衡; 缺点:没有考虑机器的性能问题&…...