【链表OJ题(三)】链表中倒数第k个结点
📝个人主页:@Sherry的成长之路
🏠学习社区:Sherry的成长之路(个人社区)
📖专栏链接:数据结构
🎯长路漫漫浩浩,万事皆有期待
文章目录
- 链表OJ题(三)
- 1. 链表中倒数第k个结点
- 思路1--两次遍历
- 思路2-快慢指针
- 2.总结:
上一篇链表OJ题链接:【链表OJ题(二)】链表的中间节点
链表OJ题(三)
1. 链表中倒数第k个结点
链接:链表中倒数第k个结点
描述:
输入一个链表,输出该链表中倒数第k个结点。
示例1::
输入:
1,{1,2,3,4,5}
返回值:
{5}
思路1–两次遍历
和求链表的中间节点的方法一相似,为直接法。
要求链表的倒数第 k 个节点,那么就是删除链表正数第 len(链表长度) - k + 1 个节点。
举个例子,例如链表长度为 5,删除倒数第 2 个节点,就是删除链表正数第 4 个节点,推导出来就是第 len + 1 - k 个节点。
所以只要先算出链表长度,然后遍历到 len + 1 - k 个节点返回即可。
注意
1.在计算出链表总长度len<k或k<=0时,直接返回NULL。
2.传递的是空链表,直接返回NULL
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
{struct ListNode*cur,*ans;cur=ans=pListHead;int len=0;while (cur) {cur=cur->next;len++;}if(k<=0||k>len)return NULL;for (int i=0; i<len-k; i++) {ans=ans->next;}return ans;
}
既然这道题目也可以用直接法,那么能否也适用于快慢指针?事实上可以,而且这道题的方法也很巧妙,接下来看思路2
思路2-快慢指针
在上一篇博客中我们也使用了快慢指针
给定一个快指针 fast 和一个慢指针 slow;我们要求链表倒数第 k 个节点,那么我们就先让快指针走 k 步;然后让 fast 和 slow 一起走,当 fast 走到空指针,这时 slow 为倒数第 k 个节点。
那么这里的原理是什么呢?
首先让 fast 走 k 步,让 fast 和 slow 的间隔为 k。链表的倒数第 k 个节点,就是正数 len + 1 - k 个节点,那么当 fast 走到空指针后,链表走完,那么现在 fast 走的距离就相当于链表的长度len + 1,fast 和 slow的间隔为 k ,那么现在的 slow 就为正数 len + 1 - k个节点,这时返回 slow就是倒数第 k 个节点。
注意
:如果在 fast 走 k 步的过程中,fast 迭代为了空指针,这时直接返回空指针。
代码:
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
{struct ListNode* fast, *slow;fast = slow = pListHead;if (pListHead == NULL)return NULL;// fast 先走 k 步while (k--)//走k次,(--k)走k-1次{// 放置 fast 先走到空if (fast == NULL){return NULL;}fast = fast->next;}// 迭代while (fast){slow = slow->next;fast = fast->next;}return slow;
}
2.总结:
今天我们通过两种思路分析并完成链表中倒数第k个结点这道链表OJ题目,也更加深层次了解和使用了快慢指针这个思路,在之后的题目中将再次出现它的使用。希望我的文章和讲解能对大家的学习提供一些帮助。
当然,本文仍有许多不足之处,欢迎各位小伙伴们随时私信交流、批评指正!我们下期见~
相关文章:

【链表OJ题(三)】链表中倒数第k个结点
📝个人主页:Sherry的成长之路 🏠学习社区:Sherry的成长之路(个人社区) 📖专栏链接:数据结构 🎯长路漫漫浩浩,万事皆有期待 文章目录链表OJ题(三)1. 链表…...

华为防火墙的学习
防火墙 - 含义和定义 什么是防火墙? 防火墙的工作原理 防火墙的区域: 包过滤防火墙----访问控制列表技术---三层技术 代理防火墙----中间人技术---应用层 状态防火墙---会话追踪技术---三层、四层 UTM---深度包检查技术----应用层 下一代防火墙 防火墙的…...

SPI 接口OLED 模块 - 兼容5V 和3.3V 电平
PCB 布局参考了老王0.8元128x32OLED显示屏转接板,开源项目地址:老王0.8元128x32OLED。 老王家买的屏幕放了快一年了,终于还是决定整个单独的模块,之前一直打算集成到开发板上的,不太灵活。相比那个转接板,主…...
css布局和定位
在Web开发中,CSS布局和定位是非常重要的技能。在这篇博客中,我们将深入探讨CSS布局和定位的概念、基本技术和最佳实践。 **CSS布局基础** ├── 盒模型 │ ├── 内边距 │ │ ├── padding │ │ ├── padding-top │ │ ├── p…...

python -- 批量读取多个文件,并将每个文件中相同变量累加
python – 批量读取多个文件,并将每个文件中相同变量累加 情况描述 现有多个nc文件,位于同一个文件夹中,如下所示每个文件中都有相同的变量,想要读取每个文件中的变量然后将其加起来意思就是说: 文件1中的变量文件2中…...

低代码开发流程是怎么样的?
低代码开发流程是怎么样的?现在很多文章都在下功夫宣传what(低代码是什么)、why(为什么要用低代码),但是很少有文章能够系统讨论how(怎么用低代码)的问题。 所以我花3天的时间准备了…...
任何时候都不要在 for 循环中删除 List 集合元素!!!
首先说结论:无论什么场景,都不要对List使用for循环的同时,删除List集合元素,因为这么做就是不对的。 阿里开发手册也明确说明禁止使用foreach删除、增加List元素。 正确删除元素的方式是使用迭代器(Iteratorÿ…...
koa+Vite+vue3+ts+pinia构建项目
一、 初始化构建项目 npm create vite myProject -- --template vue-ts 注:Vite 需要 Node.js 版本 14.18,16。然而,有些模板需要依赖更高的 Node 版本才能正常运行,当你的包管理器发出警告时,请注意升级你的 Node 版…...

k8s-yaml文件
文章目录一、K8S支持的文件格式1、yaml和json的主要区别2、YAML语言格式二、YAML1、查看 API 资源版本标签2、编写资源配置清单2.1 编写 nginx-test.yaml 资源配置清单2.2 创建资源对象2.3 查看创建的pod资源3、创建service服务对外提供访问并测试3.1 编写nginx-svc-test.yaml文…...

存储引擎
目录 ❤ MySQL存储引擎 什么是存储引擎? MySQL支持哪个存储引擎? ❤ 各种存储引擎的特性 概述 各种存储引擎的特性 各种搜索引擎介绍 ❤ 常用存储引擎及适用场景 ❤ 存储引擎在mysql中的使用 存储引擎相关sql语句 指定存储引擎建表 在建表时指定 在配置文件中…...

Go中 channel的使用
文章目录背景channel 简介使用说明声明发送和接受数据关闭channel使用示例背景 使用 sync 包和 context 包的工具可以实现多个协程之间互相协作, 但是没有一种很好的方式解决多个协程之间通信的问题. golang 作者 Rob Pike 说过一句话,不要通过共享内存来通信&…...

【C++】string OJ练习
文章目录1. 仅仅反转字母思路分析代码实现2. 字符串中的第一个唯一字符题目分析代码实现3. 《剑指offer》——替换空格解法一:寻找替换思路分析代码实现优化解法二:空间换时间思路分析代码实现4.字符串最后一个单词的长度思路分析代码实现5. 字符串相加思…...

进程间通信IPC
进程间通信IPC (InterProcess Communication) 一、进程间通信的概念 每个进程各自有不同的用户地址空间,任何一个进程的全局变量在另一个进程中都看不到,所以进程之间要交换数据必须通过内核,在内核中开辟一块缓冲区,进程1把数据…...

操作系统-页面淘汰算法(下)-软件设计(二十六)
操作系统-PV操作(上)-软件设计(二十五)https://blog.csdn.net/ke1ying/article/details/129476031 存储管理-分区存储组织 问:计算机系统内存大小为128k,当前系统分配情况如图,那么作业4再次申…...
23种设计模式-责任链模式(Android开发实际应用场景介绍)
什么是责任链模式 责任链模式是一种行为型设计模式,它的核心思想是将请求从一系列处理者中传递,直到其中一个处理者能够处理它为止。在这个过程中,请求可以被任何一个处理者处理,也可以被拒绝,直到有一个处理者能够处…...
Socket+Select+Epoll笔记
讲到epoll,就必须了解Socket,上篇博客写了Socket的基本使用方法,步骤主要为创建一个socketsocket是进程之间通信的,那么进程通信如何找到这个socket呢?当然是端口号,所以socket就要和端口号进行绑定&#x…...
git查看最近修改的文件
git log --name-status 每次修改的文件列表, 显示状态 git log --name-only 每次修改的文件列表 git log --stat 每次修改的文件列表, 及文件修改的统计 git whatchanged 每次修改的文件列表 git whatchanged --stat 每次修改的文件列表, 及文件修改的统计 git show 显示最…...
【算法基础(四)】堆排序(二)
堆排序(二) 把数组从零开始连续的一段 完全二叉树 size i 左 son 2*11 i 右 son 2*12 父 (i-1) / 2 堆是完全二叉树,分为大根堆和小根堆 在完全二叉树里,每一棵子数最大的值是头节点的值,就是大根堆 同理&…...
C++类型转换
C语言的转换是在变量前加类型名进行转换的,比如double pi 3.14;int a (int) pi;对于指针也是如此double* dptr πint* iptr (int*)dptr;虽然c兼容了C语言的转型方式,但是也做了很多限制,比如向上类型转换,在c中建议使用…...

Keil MDK6要来了,将嵌入式软件开发水平带到新高度,支持跨平台(2023-03-11)
注:这个是MDK6,不是MDK5 AC6,属于下一代MDK视频版: https://www.bilibili.com/video/BV16s4y157WF Keil MDK6要来了,将嵌入式软件开发水平带到新高度,支持跨平台一年一度的全球顶级嵌入式会展Embedded Wor…...

【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...

汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...

JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...

算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...

免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...
虚拟电厂发展三大趋势:市场化、技术主导、车网互联
市场化:从政策驱动到多元盈利 政策全面赋能 2025年4月,国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》,首次明确虚拟电厂为“独立市场主体”,提出硬性目标:2027年全国调节能力≥2000万千瓦࿰…...

【Linux】Linux 系统默认的目录及作用说明
博主介绍:✌全网粉丝23W,CSDN博客专家、Java领域优质创作者,掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围:SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...