已知一个带有表头结点的单链表,结点结构如下图。假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data值,并返回1;否则,只返回0。

时间: 2024-05-02 11:21:41 浏览: 13
算法思路: 1. 使用双指针法,让指针p和指针q同时指向表头结点。 2. 让指针q先走k步,然后让p和q同时向后移动,直到q指向空结点。 3. 当q指向空结点时,p所指向的结点就是倒数第k个结点。 4. 如果p指向的是头结点,则说明k的值大于链表长度,返回0;否则返回1并输出p所指向结点的data值。 算法实现: ```C++ int FindKthFromEnd(LinkList list, int k) { if(list == NULL || list->next == NULL) //链表为空或只有一个头结点,返回0 return 0; ListNode *p = list->next, *q = list->next; //初始化双指针 while(k--) { //让q先走k步 if(q == NULL) //如果k大于链表长度,返回0 return 0; q = q->next; } while(q != NULL) { //让p和q同时向后移动,直到q指向空结点 p = p->next; q = q->next; } if(p == list->next) //如果p指向的是头结点,说明k大于链表长度,返回0 return 0; else { printf("%d\n", p->data); //输出p所指向结点的data值 return 1; } } ```

相关推荐

最新推荐

recommend-type

通过 Matlab 测试共轭和双共轭梯度算法.zip

通过 Matlab 测试共轭和双共轭梯度算法.zip
recommend-type

基于卡尔曼估计温湿度的MATLAB程序-带交互-真实值可自己输入

背景:一维卡尔曼滤波的MATLAB例程,​背景为温度估计。 代码介绍:运行程序后,可以自己输入温度真实值 滤波前的值和滤波后的值分别于期望值(真实值)作差,可以得到​误差​曲线图 更多介绍:https://blog.csdn.net/callmeup/article/details/139374191
recommend-type

固件固件固件固件固件固件固件固件固件.txt

固件固件固件固件固件固件固件固件
recommend-type

毕业设计 - 基于JAVA的银行柜员业务绩效考核系统的设计与实现

业务绩效考核系统主要目的是使绩效考核信息管理清晰化,基本功能包括:权限处理模块、输入模块、处理模块、统计输出模块、维护模块等。本系统结构如下: 系统功能模块: 1.权限处理模块:管理员与普通柜员,管理员进入的是管理员页面,普通柜员进入普通柜员的界面。 2.输入模块 2.1 普通柜员用户注册:普通柜员通过输入用户名(工号即用户名),名字,密码进行注册,获得进入本系统权限。 2.2 柜员选择柜员身份登入:柜员进入后可以查看本人工作情况的信息。 2.3 管理员界面:登入后,记录柜员工作情况:输入柜员工号,柜员名字,记录业务笔数,最后一栏并记录柜员员工加减分情况(笔数处于10的整数部分为加减分情况,以10分为上限)。除此之外,管理员还能对普通柜员的权限进行修改,删除不必要的用户。 2.4 对管理员输入数据进行处理:比如工号只能为7位,开头必须是882;加分减分的值不能大于10等等。 3.处理模块 3.1 查询:输入柜员工号,可以查询到该柜员的工作情况以及加分减分情况及薪酬情况;按日期查询,可以查询到该日期本合作银行每位柜员的工作情况及加减分情况。 3.2
recommend-type

Raspberry Pi 脚本通过蓝牙 LE 与 Oregon Scientific 气象站对话.zip

Raspberry Pi 脚本通过蓝牙 LE 与 Oregon Scientific 气象站对话.zip
recommend-type

zigbee-cluster-library-specification

最新的zigbee-cluster-library-specification说明文档。
recommend-type

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire
recommend-type

MATLAB柱状图在信号处理中的应用:可视化信号特征和频谱分析

![matlab画柱状图](https://img-blog.csdnimg.cn/3f32348f1c9c4481a6f5931993732f97.png) # 1. MATLAB柱状图概述** MATLAB柱状图是一种图形化工具,用于可视化数据中不同类别或组的分布情况。它通过绘制垂直条形来表示每个类别或组中的数据值。柱状图在信号处理中广泛用于可视化信号特征和进行频谱分析。 柱状图的优点在于其简单易懂,能够直观地展示数据分布。在信号处理中,柱状图可以帮助工程师识别信号中的模式、趋势和异常情况,从而为信号分析和处理提供有价值的见解。 # 2. 柱状图在信号处理中的应用 柱状图在信号处理
recommend-type

hive中 的Metastore

Hive中的Metastore是一个关键的组件,它用于存储和管理Hive中的元数据。这些元数据包括表名、列名、表的数据类型、分区信息、表的存储位置等信息。Hive的查询和分析都需要Metastore来管理和访问这些元数据。 Metastore可以使用不同的后端存储来存储元数据,例如MySQL、PostgreSQL、Oracle等关系型数据库,或者Hadoop分布式文件系统中的HDFS。Metastore还提供了API,使得开发人员可以通过编程方式访问元数据。 Metastore的另一个重要功能是跟踪表的版本和历史。当用户对表进行更改时,Metastore会记录这些更改,并且可以让用户回滚到
recommend-type

JSBSim Reference Manual

JSBSim参考手册,其中包含JSBSim简介,JSBSim配置文件xml的编写语法,编程手册以及一些应用实例等。其中有部分内容还没有写完,估计有生之年很难看到完整版了,但是内容还是很有参考价值的。