GESP等级考试C++5级15-快慢指针1-云帆数科

在单链表中快慢指针是一种非常经典的算法技巧通常也被称为“龟兔赛跑算法”。它的核心思想设定两个指针从同一个起点出发以不同的速度遍历链表。在链表中使用快慢指针可以快速解决查找链表的中心结点以及倒数第i个结点的问题。1. 快速查找链表的中心结点1.1 原理使用快慢指针快速查找链表中心结点的思想是是定义两个指针初始时都指向链表首元节点。慢指针slow每次走 1 步快指针fast每次走 2 步。当快指针到达链表末尾时慢指针刚好走到链表中间。1.2 代码实现使用快慢指针快速查找链表中心结点的代码实现如图1所示。图1 使用快慢指针快速查找链表中心结点的代码其中findMiddleNode()函数是自定义函数其参数head表示链表的头结点。第22-25行代码对传入的头结点进行判断如果为NULL则直接返回NULL。第27-28行定义了结点的快慢指针。第30-34行代码通过while循环设置快慢指针的位置慢指针slow每次走 1 步快指针fast每次走 2 步。当循环结束时快指针到达链表末尾慢指针正好走到链表中间。1.3 代码运行效果在main()函数中使用图2所示代码调用findMiddleNode()函数。图2 调用findMiddleNode()函数的代码代码运行效果如图3所示。图3 代码运行效果从图3中可以看出如果链表中包含奇数个结点则findMiddleNode()函数返回的是链表的中心结点如果包含偶数个结点则findMiddleNode()函数返回的偏右的中心结点。1.4 完整代码快速查找链表中心结点的完整代码如下所示。#include iostream using namespace std; /* 在单链表中快慢指针Fast and Slow Pointers是一种非常经典的算法技巧通常也被称为“龟兔赛跑算法”。它的核心思想设定两个指针从同一个起点出发以不同的速度遍历链表。慢指针Slow每次移动 1 步slow slow-next。快指针Fast每次移动 2 步fast fast-next-next。 */ struct Node { int data; Node* next; }; /* 查找链表的中心结点如果链表中结点的个数为偶数则返回的是中心靠右的结点 */ Node* findMiddleNode(Node* head) { if (head NULL) { return NULL; } Node* slow head; Node* fast head; while(fast!NULL fast-next ! NULL)//注意循环条件 { slow slow-next; fast fast-next-next; } return slow; } Node *head, *p, *r;//r表示当前链表的尾结点p表示当前结点 int x; int main() { head new Node; r head; head-next NULL; cinx; while(x ! -1) { p new Node; p-data x; p-next NULL; r-next p; r p; cinx; } Node* mid findMiddleNode(head-next); if(mid!NULL) { coutmid-data; } return 0; }

企业数字化 ERP 产品动态

相关推荐

NVIDIA显卡故障诊断全链路指南：从现象归因到硬件快筛

1. 这不是驱动重装手册，而是一份显卡“病历本”式实战诊断笔记我干这行十多年，修过从GTX 650到RTX 4090的每一款NVIDIA消费级显卡，也陪客户在数据中心里蹲守过A100集群的GPU健康状态。但最常被问到的，从来不是“怎么装驱动”&… · 2026/9/26 5:20:06

AI聊天机器人微信小程序模板：接口接入、消息渲染与上线审核实践

简介：这款微信小程序AI机器人对话模板基于HBuilder开发，属于纯前端界面方案，未内置接口，适合具备小程序开发基础、需要快速搭建AI聊天交互页面的开发者。包内共2000个文件，以js、ts、vue、json、md等类型为主&#xff… · 2026/9/26 5:20:06

解决ReFS作为C盘文件系统找不到恢复分区的问题

这篇文章仅适用于已经长时间接触ReFS的Windows用户，如果你并不知道ReFS是什么，那么不建议继续阅读下面的内容。在ReFS作为C盘文件系统的情况下，如果你没有提前创建恢复分区，将会遇到包括但不限于以下问题：使用Windows恢… · 2026/9/26 5:20:06

【最新 v2.7.5】本地运行 Open Claw 保姆教程：5 分钟部署，用 TaoToken 统一 Key 打通自动化习惯

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/26 17:06:34

SpringBoot+Vue+MySQL招聘系统毕设全解析：从设计到部署

也到了每年毕设季扎堆的时候了。每次都有学弟学妹拿着类似的选题来问我：SpringBootVue招聘系统行不行、好不好做、有没有完整的源码项目可以抄作业。说实话，这种“SpringBootVueMySQL”三段式的全栈项目，在Java方向的毕业设计里，确… · 2026/9/26 17:06:27

macOS原生QMC解密方案：TeaCipher+动态密钥实战

简介：本资源是一款专为macOS平台开发的QQ音乐QMC加密音频格式批量转换工具，面向计算机科学、电子工程等专业学生及Python/Swift初学者，解决QMC专属格式（如qmcflac、qmc0、qmc3、mflac）无法被通用播放器识别的核心问题&… · 2026/9/26 17:06:27

基于PHP的短网址生成系统：自增ID与62进制映射原理及部署指南

简介：黑色简洁的PHP短网址/短链接生成源码是一套可直接部署的完整项目，面向需要自建短链服务的站长、网络爱好者与PHP开发者，可解决长链接冗长难记、外链地址分散、访问效果无法统计等问题。前端提供简洁优雅的响应式设计，支持创建… · 2026/9/26 17:06:27

Flutter第三方库鸿蒙化实战：音频流下载与元数据透传

年初接到一个跨平台音乐项目的鸿蒙化任务时，我原本以为只是把 Flutter 工程在 HarmonyOS 上重新编译一遍。真正开始碰soundcloud_explode_dart这个第三方库才发现，鸿蒙化的难点根本不在“能不能跑起来”，而在“跑起来之后，解析、下… · 2026/9/26 17:06:27

OpenClaw 70+技能完全指南：用 TaoToken 统一 Key 从 0 到 1 搭建 AI 自动化帝国

数据库课后习题答案别硬背：当测试用例集刷，效率翻倍

简介：万常选版《数据库原理与设计》课后习题答案资源，覆盖第2至6章及第9章，适合正在学习关系模型、数据库建模、关系数据理论与模式求精的本科生、自学者作为复习与自测材料。压缩包共7个文件，含3个doc参考答案、2个sql示例脚本、… · 2026/9/26 0:00:21

OpenClaw 替代品？Hermes Agent 踩坑实录：macOS 飞书接入 TaoToken 配置

向下兼容与向上兼容：接口设计中的兼容性策略与工程实践

一次版本升级事故，是很多团队绕不过去的坎。线上环境里，服务端明明已经上线了新版接口，老的移动端还在照着旧文档传参数。请求一到网关，校验直接拒绝，用户操作失败，客服群炸了锅，开发群里开始互… · 2026/9/26 0:00:46

GESP等级考试C++5级15-快慢指针1

相关推荐

了解更多？预约专属演示