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

【PTA刷题】求链式线性表的倒数第K项(代码+详解)

文章目录

    • 题目
    • 代码
    • 详解

题目

给定一系列正整数,请设计一个尽可能高效的算法,查找倒数第K个位置上的数字。

输入格式:

输入首先给出一个正整数K,随后是若干非负整数,最后以一个负整数表示结尾(该负数不算在序列内,不要处理)。

输出格式:

输出倒数第K个位置上的数据。如果这个位置不存在,输出错误信息NULL

输入样例:

4 1 2 3 4 5 6 7 8 9 0 -1

输出样例:

7

代码

#include <stdio.h>
#include <stdlib.h>// 定义链表节点结构
struct ListNode {int val;struct ListNode* next;
};// 查找倒数第K个位置上的数字
int findKthFromEnd(struct ListNode* head, int k) {if (!head || k <= 0) return -1; // 如果链表为空或k小于等于0,返回-1表示错误struct ListNode* slow = head;struct ListNode* fast = head;// 快指针先移动k步for (int i = 0; i < k; ++i) {if (!fast) return -1; // 如果链表长度小于k,返回-1表示错误fast = fast->next;}// 同时移动慢指针和快指针,直到快指针到达链表尾部while (fast) {slow = slow->next;fast = fast->next;}return slow->val;
}int main() {int k;scanf("%d", &k);int num;struct ListNode* head = NULL;struct ListNode* tail = NULL;// 构建链表while (scanf("%d", &num) && num >= 0) {struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));newNode->val = num;newNode->next = NULL;if (!head) {head = newNode;tail = newNode;} else {tail->next = newNode;tail = newNode;}}int result = findKthFromEnd(head, k);if (result != -1) {printf("%d\n", result);} else {printf("NULL\n");}// 释放链表内存while (head) {struct ListNode* temp = head;head = head->next;free(temp);}return 0;
}

详解

这个问题要求找出一个正整数序列中倒数第K个元素的值。为了解决这个问题,代码使用了一个快慢指针的方法,并且用链表来存储输入的序列。下面是对这个算法和代码的详细解释:

算法逻辑

  1. 使用快慢指针:

    • 快指针 (fast) 和慢指针 (slow) 都从链表的头结点开始。
    • 先让快指针向前移动K步。这样,快慢指针之间就保持了K个节点的距离。
    • 然后,同时移动快指针和慢指针,直到快指针到达链表的末尾。此时,慢指针所在的位置就是倒数第K个节点。
  2. 边界条件处理:

    • 如果链表为空(head == NULL),或者K值不合理(k <= 0),函数直接返回-1,表示错误。
    • 如果链表长度小于K,也就是快指针在移动K步之前已经到达了链表末尾,函数同样返回-1。

代码解释

  1. 链表节点定义:

    • struct ListNode 定义了链表的节点结构,包括节点值 val 和指向下一个节点的指针 next
  2. 主函数 main:

    • 读取K值。
    • 通过循环读取输入的正整数,并构建链表。遇到负数时停止读取。
    • 调用 findKthFromEnd 函数来查找倒数第K个元素的值。
  3. 查找函数 findKthFromEnd:

    • 初始化快慢指针。
    • 让快指针先移动K步。
    • 同时移动快慢指针,直到快指针到达末尾。
    • 返回慢指针所指向的节点的值。
  4. 输出结果:

    • 如果返回值不是-1,则输出该值。
    • 如果返回值是-1,输出"NULL"。
  5. 释放内存:

    • 循环释放链表的每个节点,避免内存泄露。

这个算法的时间复杂度是O(n),因为它最多遍历链表两次:一次用于构建链表,一次用于找到倒数第K个元素。

相关文章:

【PTA刷题】求链式线性表的倒数第K项(代码+详解)

文章目录 题目代码详解 题目 给定一系列正整数&#xff0c;请设计一个尽可能高效的算法&#xff0c;查找倒数第K个位置上的数字。 输入格式: 输入首先给出一个正整数K&#xff0c;随后是若干非负整数&#xff0c;最后以一个负整数表示结尾&#xff08;该负数不算在序列内&#…...

VSCode 创建工作区,多文件夹终端切换

VSCode 创建工作区的好处有以下几点&#xff1a; 项目结构清晰&#xff1a;每个工作区都有自己的文件夹结构&#xff0c;可以更好地组织和管理项目文件。版本控制&#xff1a;VSCode 支持多种版本控制系统&#xff0c;如Git&#xff0c;可以在工作区内进行代码的版本管理。插件…...

高阶函数(js的问题)

&#xff08;1&#xff09;函数可以作为参数被传递 &#xff08;2&#xff09;函数可以作为返回值输出 4-1.函数作为参数传递 Array.prototype.sort方法&#xff1a; var array [10,5,12,3];array.sort();//array:[10,12,3,5]//如代码那样&#xff0c;排序的结果并不是我们想要…...

android-android源码目录

android源码目录 Android.bp art bionic bootable bootstrap.bash build build.sh compatibility cts dalvik developers development device external frameworks: Android 系统的核心框架代码av: 该目录包含与音视频相关的框架和库&#xff0c;如音频解码器、视频编码器、多…...

Json格式化

Json格式化 大家好&#xff0c;我是微赚淘客机器人的小编&#xff0c;也是冬天不穿秋裤&#xff0c;天冷也要风度的程序猿&#xff01; Json格式化&#xff1a;让数据更亮眼&#xff0c;解密Json的奇妙世界 在现代Web开发中&#xff0c;Json&#xff08;JavaScript Object N…...

数据可视化设计:让数据故事更有说服力

写在开头 在数字化的时代,数据如同一把锁住的宝剑,等待我们挥舞。然而,唯有通过巧妙运用数据可视化的原则和技术,我们才能真正解锁数据的力量,创造出令人信服的数据故事。本文将深入研究数据可视化设计的奥秘,揭示其中的魔法,让你在数据的海洋中游刃有余,用数据的语言…...

java面试题-Spring事务以及@Transactional注解详解

远离八股文&#xff0c;面试大白话&#xff0c;通俗且易懂 看完后试着用自己的话复述出来。有问题请指出&#xff0c;有需要帮助理解的或者遇到的真实面试题不知道怎么总结的也请评论中写出来&#xff0c;大家一起解决。 java面试题汇总-目录-持续更新中 对于这个面试中高频问到…...

ARM流水灯

.text .global _start _start: LED1 1.RCC时钟使能GPIOE RCC_MP_AHB4ENSETR[4]->1 LDR R0,0x50000a28 LDR R1,[R0] ORR R1,R1,#(0x1<<4) STR R1,[R0] 2.设置PE10为输出模式 GPIOE_MODER[21:20]->01 先清0 LDR R0,0x50006000 LDR R1,[R0] BIC R1,R1,#(0x3<&…...

docker-compose单机容器编排

Dockerfile:先配置好文件&#xff0c;然后build&#xff0c;镜像-------->容器。 docker-conpose 既可以基于dockerfile,也可以基于镜像&#xff0c;一键式拉起镜像和容器。 docker-compose核心就是yml文件&#xff0c;可以定义容器的一切。通过yml配置&#xff0c;直接运行…...

matlab信号分选系统算法-完整算法结构

matlab信号分选系统算法 针对得到的脉冲流PDW进行信号分选&#xff0c;包括重频恒定、重频抖动、重频参差和重频滑变四种脉间调制类型。   这里我们先进行数据的仿真&#xff0c;后续边仿真边分享思路&#xff1a;首先根据信号类型&#xff0c;分别产生重频恒定、重频抖动、重…...

十八)Stable Diffusion使用教程:艺术二维码案例

今天说说怎么样使用SD生成艺术二维码。 我们直接上图。 方式有三种,分别如下: 1)方式一:直接 contronet 的tile模型进行控制 使用QRBTF Classic生成你的二维码。 首先输入网址,选择喜欢的二维码样式(推荐第一种就行): 然后选择相应参数,这里推荐最大的容错率,定…...

【LeetCode每日一题】53. 最大子数组和

https://leetcode.cn/problems/maximum-subarray/description/ 给你一个整数数组 nums &#xff0c;请你找出一个具有最大和的连续子数组&#xff08;子数组最少包含一个元素&#xff09;&#xff0c;返回其最大和。 子数组 是数组中的一个连续部分。 方式一&#xff1a;暴力…...

机器学习笔记 什么是协方差矩阵?

一、协方差矩阵 协方差矩阵是一种矩阵,用于表示随机向量中给定的元素对之间的协方差值。协方差矩阵也可以称为色散矩阵或方差-协方差矩阵。这是因为每个元素的方差是沿着矩阵的主对角线表示的。 协方差矩阵始终是方阵。此外,它是半正定且对称的。该矩阵在随机建模和主成分分析…...

使用Python监控服务器在线状态

前言 在公司内网有一台服务器&#xff0c;有动态的公网IP&#xff0c;使用DDNS对外提供服务&#xff0c;但是会因为停电、服务器卡死等原因导致服务器离线。服务器离线后无法及时获知&#xff0c;因此需要实现在服务器离线的时候能够发送消息到手机上。 思路梳理 公司办理的…...

【JAVA】黑马MybatisPlus 学习笔记【二】【核心功能】

2.核心功能 刚才的案例中都是以id为条件的简单CRUD&#xff0c;一些复杂条件的SQL语句就要用到一些更高级的功能了。 2.1.条件构造器 除了新增以外&#xff0c;修改、删除、查询的SQL语句都需要指定where条件。因此BaseMapper中提供的相关方法除了以id作为where条件以外&…...

区块链实验室(30) - 区块链期刊:Distributed Ledger Technologies: Research and Practice

区块链涉及多学科及技术&#xff0c;众多期刊接收区块链文章。Distributed Ledger Technologies: Research and Practice是ACM出版集团的一本期刊。 Distributed Ledger Technologies: Research and Practice创刊历史很短&#xff0c;始于2022年&#xff0c;出版期数也不多。 载…...

Nginx【通俗易懂】《中篇》

目录 1.Url重写rewrite 2.防盗链 3.静态资源压缩 4.跨域问题 1.Url重写rewrite &#x1f929;&#x1f929;&#x1f929; 1.1.rewrite书写格式 rewrite是实现URL重写的关键指令&#xff0c;根据regex&#xff08;正则表达式&#xff09;部分内容&#xff0c;重定向到rep…...

组件的二次封装

在React中&#xff0c;使用扩展运算符&#xff08;...&#xff09;来传递props的作用是将一个对象的所有可枚举属性&#xff08;包括自身的和继承的&#xff09;复制到新创建的对象中。当我们在二次封装组件时使用它&#xff0c;可以方便地将所有传递给我们的props传递给基础组…...

curl+postman 在java开发中的使用(提高效率)

概念 curl 是一个常用的命令行工具&#xff0c;用于发送各种类型的 HTTP 请求&#xff0c;包括 GET、POST、PUT、DELETE 等。它也可以用来下载文件、上传文件、设置 cookie、发送 multipart/form-data 等等。 使用 调用post接口 实际中的接口&#xff1a; curl --location…...

【电子取证:FTK IMAGER 篇】DD、E01系统镜像动态仿真

​ 文章目录 【电子取证&#xff1a;FTK Imager 篇】DD、E01系统镜像动态仿真一、DD、E01系统镜像动态仿真 &#xff08;一&#xff09;使用到的软件 1、FTK Imager (v4.5.0.3)2、VMware Workstation 15 Pro (v15.5.2)&#xff08;二&#xff09;FTK Imager 挂载镜像 1、选择 …...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...

逻辑回归暴力训练预测金融欺诈

简述 「使用逻辑回归暴力预测金融欺诈&#xff0c;并不断增加特征维度持续测试」的做法&#xff0c;体现了一种逐步建模与迭代验证的实验思路&#xff0c;在金融欺诈检测中非常有价值&#xff0c;本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...

比较数据迁移后MySQL数据库和OceanBase数据仓库中的表

设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...

【Linux】自动化构建-Make/Makefile

前言 上文我们讲到了Linux中的编译器gcc/g 【Linux】编译器gcc/g及其库的详细介绍-CSDN博客 本来我们将一个对于编译来说很重要的工具&#xff1a;make/makfile 1.背景 在一个工程中源文件不计其数&#xff0c;其按类型、功能、模块分别放在若干个目录中&#xff0c;mak…...