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

【基础算法】单链表的OJ练习(2) # 链表的中间结点 # 链表中倒数第k个结点 #

文章目录

  • 前言
  • 链表的中间结点
  • 链表中倒数第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;
}

思路二

  • 该做法为快慢指针。

  • 啥为快慢指针呢?在本题有关当中,我们定义两个指针指向链表的头节点,并且共同遍历链表,不同的是,一个指针每一次走两步,另一个指针每次走一步,这就是快慢指针。

  • 每当快指针满足循环结束条件,慢指针都是指向链表的中间节点的。因为快指针走两步,慢指针走一步,整个移动的位移差相差一倍,所以每当快指针满足结束条件的时候,慢指针走的步数都是快指针走的步数的一半, 因此慢指针指向的那个节点就是整个链表的中间节点。

  • 快指针结束的条件有两种情况,一种是快指针刚好指向空结束,一种是快指针指向尾节点结束,也就是快指针的nextNULL

1.当快指针刚好指向NULL结束,此时链表的节点个数为偶数:

在这里插入图片描述

2.当快指针指向尾节点结束,也就是快指针的nextNULL,此时链表的节点个数为奇数:

在这里插入图片描述

代码实现:

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练习&#xff0c;需要深刻理解做题的思路&#xff0c;这样我们才能够在任何场景都能够熟练的解答有关链表的问题。 关于OJ练习&#xff08;1&#xff09;&#xff1a;-> 传送门 <-&#xff0c…...

vue路由文件拆分管理

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

实例解析Java反射

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

Android 9适配经验总结

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

定时任务调度方案——Xxl-Job

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

操作系统引导

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

[C#] 多线程单例子,分为阻塞型和分阻塞型, 在unity里的应用

在单例中使用多线程时&#xff0c;需要注意以下几点&#xff1a; 线程安全&#xff1a;在多线程环境下&#xff0c;单例对象可能被多个线程同时访问&#xff0c;因此需要确保单例的线程安全&#xff0c;避免出现数据竞争等问题。 对象创建&#xff1a;如果在单例对象的构造函数…...

使用MAT进行内存分析,并找到OOM问题

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

初识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 &#xff0c;在字节码文件中对应多个指令&#xff0c;多个线程在运行多个指令时&#xff0c;就存在原子性、可见性问题 赋值 多线程场景下&#xff0c;一个指令如果包含多个字节码指令&#xff0c;那么就不再是原子操作。因为赋值的同时&#xff0c…...

错误:EfficientDet网络出现“No boxes to NMS“并且mAP:0.0的解决方案

近日&#xff0c;在使用谷歌新推出来的一个网络EfficientDet进行目标检测训练自己的数据集的时候&#xff0c;出现了如下错误&#xff1a; 其中项目开源地址是&#xff1a;https://github.com/toandaominh1997/EfficientDet.Pytorch 上面截图中的1和2代表我的类别名称。读者可…...

python的opencv操作记录13——区域生长及分水岭算法

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

一文看懂网上下单的手机流量卡为什么归属都是随机的!

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

python Pytest生成alluer测试报告的完整教程

1.下载allure包到本地&#xff0c;解压 网上很多资料&#xff0c;这边不提供了 2.配置环境变量 将上面解压后bin文件的路径复制&#xff0c;添加到环境变量Path下 3.验证环境变量配置是否功 在cmd中输入allure&#xff0c;回车 。查看allure是否成功&#xff1a; 4.pyc…...

4-spring篇

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

提升 Web 应用程序的性能:如何使用 JavaScript 编写缓存服务

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

供应商绩效管理指南:挑战、考核指标与管理工具

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

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

android RelativeLayout布局

<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...

【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅

目录 前言 操作系统与驱动程序 是什么&#xff0c;为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中&#xff0c;我们在使用电子设备时&#xff0c;我们所输入执行的每一条指令最终大多都会作用到硬件上&#xff0c;比如下载一款软件最终会下载到硬盘上&am…...

通过MicroSip配置自己的freeswitch服务器进行调试记录

之前用docker安装的freeswitch的&#xff0c;启动是正常的&#xff0c; 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...