网站强制使用极速模式/农村电商平台
欢迎来到 Claffic 的博客 💞💞💞
前言:
快慢指针指的是每次指针移动的步长,是解决链表相关的题目的一大利器,下面我将以例题的形式讲解快慢指针法。
目录
一. 链表的中间结点
思路:
代码实现:
二. 链表中倒数第k个结点
思路:
代码实现:
三. 判断链表中是否有环
思路:
代码实现:
四. 返回链表入环的第一个结点
思路:
代码实现:
一. 链表的中间结点
点我做题
思路:
创建两个快慢指针 slow , fast ,起始共同指向头节点,slow 每次走一步,fast 每次走两步,当 fast 为空或 fast 的下一个结点为空时,slow 即是中间节点的位置。
解释:
由于 fast 每次走两步,slow 每次走一步,slow 总是落后 fast 整体一半的长度最终 slow 理应为中间结点。
结点数为奇数:
最终 fast 在最后一个结点,此时结束的标志为 fast->next == NULL;
结点数为偶数:
最终 fast 在最后一个结点的下一个指向,此时的结束标志为 fast == NULL;
代码实现:
struct ListNode* middleNode(struct ListNode* head){struct ListNode* slow,*fast;slow = head;fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}
二. 链表中倒数第k个结点
点我做题
思路:
同样,创建两个快慢指针 slow , fast ,起始共同指向头节点,先让 fast 走 k 步,再让 fast 和 slow 同时前进,直到 fast 为空为止。
解释:
先让 fast 走 k 步,那么 fast 与 slow 之间就隔了 k-1 个结点,fast 与 slow 同时前进,直到 fast 为空时,fast 与 slow 之间依然隔 k-1 个结点,那就是倒数第 k 个结点。
代码实现:
int kthToLast(struct ListNode* head, int k){struct ListNode* fast,*slow;fast = slow = head;if(head == NULL){return NULL;}//fast 前进 k 步while(k--){fast = fast->next;}//slow 与 fast 共同前进while(fast){slow = slow->next;fast = fast->next;}//注意返回的是整型数值return slow->val;
}
三. 判断链表中是否有环
点我做题
思路:
快慢指针 slow , fast,都从 head 开始,slow 一次走一步,fast 一次走两步,如果 slow 和 fast 能相遇,则链表有环。
解释:
主要是证明 有环情况下两个指针一定能相遇:
fast 比 slow 先进入环,如图,假设 slow 和 fast 的位置,这两个指针之间差 N 步,
由于 fast 每次走两步,slow 每次走一步,所以 slow 和 fast 之间的距离每次缩短 1
N - 1
N - 2
N - 3
...
2
1
0 //此时两者相遇
证毕。
代码实现:
bool hasCycle(struct ListNode* head) {struct ListNode* fast,*slow;fast = slow = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(fast == slow){return true;}}return false;
}
四. 返回链表入环的第一个结点
点我做题
思路:
这里要先放一个结论:
在链表有环的情况下,一个指针在起始结点开始走,另一个结点在相遇点开始走,最终两个指针会在入环点相遇。
快慢指针 slow , fast,都从 head 开始,slow 一次走一步,fast 一次走两步,找到相遇点后,再让 start 与 meet 同时前进,两者相等的点即是入环点。
解释:
自然要证明上边的结论:
在这里,我们设几个常量:
L:起始点到入环点的距离;
X:入环点到相遇点的距离;
C:环的周长。
已知条件:
slow 走的距离:L + X ;
fast 走的距离:L + n*C + X (n >=1) ;
fast 走的长度是 slow 走的长度的 2 倍。
推导:
fast 走的长度是 slow 走的长度的 2 倍 -->
2*(L + X) == L + n*C + X (n >=1),
整理得:L == C - X + (n - 1)*C (n >=1).
对 L == C - X + (n - 1)*C (n >=1) 的解释:
C - X + (n - 1)*C (n >=1) 原本是 meet 到 innode 要走的所有可能距离,
而 L == C - X + (n - 1)*C (n >=1) ,说明 start 到 innode 要走的距离与 meet 到 innode 要走的所有可能距离相等,所以两者相遇的点一定是 innode.
代码实现:
struct ListNode* detectCycle(struct ListNode *head) {struct ListNode* slow,*fast;slow = fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast){struct ListNode* meet = slow;struct ListNode* start = head;while(meet != start){meet = meet->next;start = start->next;}return meet;}}return NULL;
}
总结:
快慢指针是解决链表问题的一大利器,建议多画图理解掌握。
码文不易
如果你觉得这篇文章还不错并且对你有帮助,不妨支持一波哦 💗💗💗
相关文章:

链表OJ之 快慢指针法总结
欢迎来到 Claffic 的博客 💞💞💞 前言: 快慢指针指的是每次指针移动的步长,是解决链表相关的题目的一大利器,下面我将以例题的形式讲解快慢指针法。 目录 一. 链表的中间结点 思路: 代码实…...

C++STL详解(五)——list的介绍与使用
文章目录list的介绍list的使用list的定义方法list迭代器失效问题list插入和删除inserteraselist迭代器的使用begin,end 和 rbegin,rendlist元素访问front 和 backlist容量控制与数据清理resizeclearlist操作函数spliceremove 和 remove_ifuniquemergerev…...

进程和进程的调度
今天,为大家带来进程和进程的调度的学习 1.认识计算机 2.什么是操作系统 3.什么是进程 4.进程管理 5.进程的属性 6.进程的调度 7.进程调度的过程 8.内存分配 1.认识计算机 计算机的组成有五大部分 1.CPU(是计算机的大脑,负责逻辑运算和控制) 2.内存 3.外存 4.输入…...

TypeScript 深度剖析:TypeScript 的理解?与 JavaScript 的区别?
一、是什么 TypeScript 是 JavaScript 的类型的超集,支持ES6语法,支持面向对象编程的概念,如类、接口、继承、泛型等 超集,不得不说另外一个概念,子集,怎么理解这两个呢,举个例子,如…...

美颜SDK关键技术讲解——人脸识别与人脸美化
拍摄,自从智能手机普及之后就已经不再是小众爱好,使用手机拍摄记录生活几乎成了人们的日常。在巨量的需求下,美颜工具、美颜SDK已经被广泛应用于各大视频拍摄平台。虽然经常听到美颜SDK,但是大多数人并不了解它,下文小…...

Linux下C/C++ 网络扫描(主机扫描技术)
主机扫描是网络扫描的基础,通过对目标网络中主机IP地址的扫描,从一堆主机中扫描出存活的主机,然后以他们为目标进行后续的攻击。一般会借助于ICMP、TCP、UDP等协议的工作机制,检查打开的进程,开放的端口号等等。 主机…...

无法将“vue-cli-service”项识别为 cmdlet、函数、脚本文件或不是内部命令的原因和解决方案
经常有小伙伴问我说,为什么我们在开发vue项目的时候,需要在package.json的script对象中,去设置命令启动项目,而不是直接的通过"vue-cli-service serve"命令去把项目跑起来。带着这些疑问,小生在此总结了以下…...

逆流程 场景下 处理状态机变化的方案
背景: 针对某些业务场景下,存在逆流程。 比如场景的场景 正向流程如,发起某项申请->对某项申请进行审批。(审批为通过/驳回)。这样这个工作流程就算到最终态。 常见的状态机如, 申请未提交࿰…...

【剧前爆米花--爪哇岛寻宝】Java实现无头单向非循环链表和无头双向链表与相关题目
作者:困了电视剧 专栏:《数据结构--Java》 文章分布:这是关于数据结构链表的文章,包含了自己的无头单向非循环链表和无头双向链表实现简单实现,和相关题目,想对你有所帮助。 目录 无头单向非循环链表实现 …...

学习MvvmLight工具
最近学习了一下MvvmLight,觉得有些功能还是挺有特色的,所以记录一下 首先新建也给WPF程序 然后在Nuget里面安装MvvmLightLib 包,安装上面那个也可以,但是安装上面那个会自动在代码里面添加一些MvvmLight的demo ,安装M…...

基于BiLSTM+CRF医学病例命名实体识别项目
研究背景 为通过项目实战增加对命名实体识别的认识,本文找到中科院软件所刘焕勇老师在github上的开源项目,中文电子病例命名实体识别项目MedicalNamedEntityRecognition。对其进行详细解读。 原项目地址:https://github.com/liuhuanyong/Med…...

05 C语言数据类型
05 C语言数据类型 1、数据类型 编程语言对数据类型分为两派:一种认为要注重,一种认为可以忽视。 C语言类型 1、整数 : char < short < int < long < long long ,bool 2、浮点数:float < double < long doub…...

C++11:右值引用和移动语义
文章目录1. 左值和右值表达式1.1 概念1.2 左值和右值2. 左值引用和右值引用2.1 相互引用2.2 示例代码2.3 左值引用使用场景缺点2.4 右值引用和移动语义小结2.5 移动赋值2.6 右值引用的其他使用场景右值引用版本的插入函数3. 完美转发3.1 万能引用3.2 如何实现完美转发3.3 完美转…...

tcpdump网络抓包工具
tcpdump 是一个强大的网络抓包工具,在分析服务之间调用时非常有用。可以将网络中传送的数据包抓取下来进行分析。tcpdump 提供灵活的抓取策略,支持针对网络层、协议、主机、网络或端口的过滤,并提供 and、or、not 等逻辑语句来去掉不想要的信…...

MaxCompute SQL中的所有保留字与关键字如下
– MaxCompute SQL中的所有保留字与关键字如下 注意 命名表、列或分区时,不要使用保留字与关键字,否则可能会报错。 保留字不区分大小写。 在对表、列或是分区命名时如若使用关键字,需给关键字加符号进行转义,否则会报错。 % &am…...

Kafka 压缩算法
压缩 (compression) : 用时间换空间的思想 用较小的 CPU 开销获得磁盘少占用或网络 I/O 少传输 Kafka 消息分两层: 消息日志组成 : n 个消息集合消息集合 (message set) 组成 : n 条日志项 (record item)日志项封装了消息 (message)Kafka 在消息集合层上进行写入…...

关于React Hook(18)
useState():👉详情 (必须“有条件地调用”;注意避免冗余状态的产生) 关于useState的两种使用方式的区别:👉详情 关于batch机制:有条件地调用一些状态的set方…...

计算机网络:BGP协议
BGP协议 与其他AS的邻站BPG发言人交换信息。 交换的网络可达性信息,即要到达某一个网络所要经历的一系列AS 发生变化时,更新有变化的部分 BGP协议交换信息的过程:所交换的网络可达性信息就是要到达某一个网络所要经历的一系列ASÿ…...

91. 解码方法 ——【Leetcode每日刷题】
91. 解码方法 一条包含字母 A-Z 的消息通过以下映射进行了 编码 : ‘A’ -> “1” ‘B’ -> “2” … ‘Z’ -> “26” 要 解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法࿰…...

人体存在传感器成品方案,精准感知静止存在,实时智能化感控技术
随着现今智能时代的发展,酒店也越来越趋于智能化,也在不断地推行智慧酒店,这也给人们入住酒店提供了良好的体验。 人体存在感知是智能酒店中极其重要的一项应用技术,只有智能设备通过精准地感知人体存在,才能更好地做…...

mysql连接池的实现
目录 1 池化技术 2 什么是数据库连接池 3 为什么使用数据库连接池 3.1 不使用连接池 3.2 使用连接池 3.3 长连接和连接池的区别 4 数据库连接池运行机制 5 连接池和线程池的关系 6 线程池设计要点 6.1 连接池设计逻辑 构造函数 初始化 请求获取连接 归还连接 析…...

哪种类型蓝牙耳机佩戴最舒服?舒适度最好的蓝牙耳机推荐
如果您想在外出时听自己喜欢的音乐,您需要佩戴耳机,当前的耳机都足够小,可以将它们放在口袋里,即使它们在充电盒中也是如此,舒适度一直都是人们所追求的,舒适之余,佩戴同样稳固更加令人安心&…...

2020蓝桥杯真题洁净数 C语言/C++
题目描述 小明非常不喜欢数字 2,包括那些数位上包含数字 2 的数。如果一个数的数位不包含数字 2,小明将它称为洁净数。 请问在整数 1 至 n 中,洁净数有多少个? 输入描述 输入的第一行包含一个整数 n(1≤n≤10^6)。 输出描述 输…...

【随笔二】useReducer详解及其应用场景
前言 useReducer 实际上是 useState 的升级版,都是用来存储和更新 state,只是应用的场景不一样。 一般情况下,我们使用 useState 就足够项目需要了,不多当遇到以下场景时,使用useReducer 会更好些 。 状态逻辑复杂&…...

打怪升级之istringstream介绍
istringstream类 istringstream本质不是类,是一个宏,或者说是一个流: typedef basic_istringstream<char> istringstream;istringstream从basic_istringstream的char专用项而来。这一部分让人看得摸不着头脑的原因是因为大量使用了st…...

系统重装漏洞
zzcms系统重装漏洞 一、配置zzcms环境 1. 使用小皮搭建zzcms框架 2. 安装zzcms 按照下面的操作进行,傻瓜式操作即可 3. 打开网站 二、漏洞利用 在访问install目录的默认文件后,会出现zzcms安装向导 http://www.zzcms.com/install/index.php 但是会显示 “安装向导…...

C++面向对象编程之五:友元(friend)
C中,允许一个类的非共有成员被这个类授予友元(friend)关系的全局函数,另一个类,或另一个类中的成员函数访问。友元不是一个类中的成员,所以它们不受声明出现部分的访问权限(public,p…...

[手写OS]动手实现一个OS 之X86实模式下的汇编开发
[手写OS]动手实现一个OS 之X86实模式下的汇编开发 x86实模式下 汇编开发是一个 intel x86实模式中的汇编程序开发类型。它涉及操纵几个16位处理器寄存器,并仅处理内存中的物理地址(与受保护模式相对)。 这种类型的编程中最广为人知的应用就…...

【Linux内核二】常用的网络丢包错包debug工具介绍
目录 ifconfig Ifconfig输出各字段简述 txqueuelen RX和TX的errors指哪些错误 dropped与overruns的区别 常用ifconfig配置命令 显示网卡信息 启动关闭指定网卡 配置和删除ip地址 修改MAC地址 启用和关闭ARP协议 设置最大传输单元 设置网卡的promiscuous模式 设置…...

qt控件增加渐变色效果
ui->returnBtn->setStyleSheet("color: rgb(0, 0, 0);""background:qlineargradient(spread:pad, x1:0, y1:1, x2:0, y2:0, ""stop:0 #5f5f5f, stop:0.5 #ffffff, stop:0.98 #5f5f5f);""border:none;");效果如下图: …...