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

【链表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个结点

​ ​&#x1f4dd;个人主页&#xff1a;Sherry的成长之路 &#x1f3e0;学习社区&#xff1a;Sherry的成长之路&#xff08;个人社区&#xff09; &#x1f4d6;专栏链接&#xff1a;数据结构 &#x1f3af;长路漫漫浩浩&#xff0c;万事皆有期待 文章目录链表OJ题(三)1. 链表…...

华为防火墙的学习

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

SPI 接口OLED 模块 - 兼容5V 和3.3V 电平

PCB 布局参考了老王0.8元128x32OLED显示屏转接板&#xff0c;开源项目地址&#xff1a;老王0.8元128x32OLED。 老王家买的屏幕放了快一年了&#xff0c;终于还是决定整个单独的模块&#xff0c;之前一直打算集成到开发板上的&#xff0c;不太灵活。相比那个转接板&#xff0c;主…...

css布局和定位

在Web开发中&#xff0c;CSS布局和定位是非常重要的技能。在这篇博客中&#xff0c;我们将深入探讨CSS布局和定位的概念、基本技术和最佳实践。 **CSS布局基础** ├── 盒模型 │ ├── 内边距 │ │ ├── padding │ │ ├── padding-top │ │ ├── p…...

python -- 批量读取多个文件,并将每个文件中相同变量累加

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

低代码开发流程是怎么样的?

低代码开发流程是怎么样的&#xff1f;现在很多文章都在下功夫宣传what&#xff08;低代码是什么&#xff09;、why&#xff08;为什么要用低代码&#xff09;&#xff0c;但是很少有文章能够系统讨论how&#xff08;怎么用低代码&#xff09;的问题。 所以我花3天的时间准备了…...

任何时候都不要在 for 循环中删除 List 集合元素!!!

首先说结论&#xff1a;无论什么场景&#xff0c;都不要对List使用for循环的同时&#xff0c;删除List集合元素&#xff0c;因为这么做就是不对的。 阿里开发手册也明确说明禁止使用foreach删除、增加List元素。 正确删除元素的方式是使用迭代器&#xff08;Iterator&#xff…...

koa+Vite+vue3+ts+pinia构建项目

一、 初始化构建项目 npm create vite myProject -- --template vue-ts 注&#xff1a;Vite 需要 Node.js 版本 14.18&#xff0c;16。然而&#xff0c;有些模板需要依赖更高的 Node 版本才能正常运行&#xff0c;当你的包管理器发出警告时&#xff0c;请注意升级你的 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 说过一句话&#xff0c;不要通过共享内存来通信&…...

【C++】string OJ练习

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

进程间通信IPC

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

操作系统-页面淘汰算法(下)-软件设计(二十六)

操作系统-PV操作&#xff08;上&#xff09;-软件设计&#xff08;二十五&#xff09;https://blog.csdn.net/ke1ying/article/details/129476031 存储管理-分区存储组织 问&#xff1a;计算机系统内存大小为128k&#xff0c;当前系统分配情况如图&#xff0c;那么作业4再次申…...

23种设计模式-责任链模式(Android开发实际应用场景介绍)

什么是责任链模式 责任链模式是一种行为型设计模式&#xff0c;它的核心思想是将请求从一系列处理者中传递&#xff0c;直到其中一个处理者能够处理它为止。在这个过程中&#xff0c;请求可以被任何一个处理者处理&#xff0c;也可以被拒绝&#xff0c;直到有一个处理者能够处…...

Socket+Select+Epoll笔记

讲到epoll&#xff0c;就必须了解Socket&#xff0c;上篇博客写了Socket的基本使用方法&#xff0c;步骤主要为创建一个socketsocket是进程之间通信的&#xff0c;那么进程通信如何找到这个socket呢&#xff1f;当然是端口号&#xff0c;所以socket就要和端口号进行绑定&#x…...

git查看最近修改的文件

git log --name-status 每次修改的文件列表, 显示状态 git log --name-only 每次修改的文件列表 git log --stat 每次修改的文件列表, 及文件修改的统计 git whatchanged 每次修改的文件列表 git whatchanged --stat 每次修改的文件列表, 及文件修改的统计 git show 显示最…...

【算法基础(四)】堆排序(二)

堆排序&#xff08;二&#xff09; 把数组从零开始连续的一段 完全二叉树 size i 左 son 2*11 i 右 son 2*12 父 (i-1) / 2 堆是完全二叉树&#xff0c;分为大根堆和小根堆 在完全二叉树里&#xff0c;每一棵子数最大的值是头节点的值&#xff0c;就是大根堆 同理&…...

C++类型转换

C语言的转换是在变量前加类型名进行转换的&#xff0c;比如double pi 3.14;int a (int) pi;对于指针也是如此double* dptr &pi;int* iptr (int*)dptr;虽然c兼容了C语言的转型方式&#xff0c;但是也做了很多限制&#xff0c;比如向上类型转换&#xff0c;在c中建议使用…...

Keil MDK6要来了,将嵌入式软件开发水平带到新高度,支持跨平台(2023-03-11)

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

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...

零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程

STM32F1 本教程使用零知标准板&#xff08;STM32F103RBT6&#xff09;通过I2C驱动ICM20948九轴传感器&#xff0c;实现姿态解算&#xff0c;并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化&#xff0c;适合嵌入式及物联网开发者。在基础驱动上新增…...

uniapp 实现腾讯云IM群文件上传下载功能

UniApp 集成腾讯云IM实现群文件上传下载功能全攻略 一、功能背景与技术选型 在团队协作场景中&#xff0c;群文件共享是核心需求之一。本文将介绍如何基于腾讯云IMCOS&#xff0c;在uniapp中实现&#xff1a; 群内文件上传/下载文件元数据管理下载进度追踪跨平台文件预览 二…...

【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?

FTP&#xff08;File Transfer Protocol&#xff09;本身是一个基于 TCP 的协议&#xff0c;理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况&#xff0c;主要原因包括&#xff1a; ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...

Java详解LeetCode 热题 100(26):LeetCode 142. 环形链表 II(Linked List Cycle II)详解

文章目录 1. 题目描述1.1 链表节点定义 2. 理解题目2.1 问题可视化2.2 核心挑战 3. 解法一&#xff1a;HashSet 标记访问法3.1 算法思路3.2 Java代码实现3.3 详细执行过程演示3.4 执行结果示例3.5 复杂度分析3.6 优缺点分析 4. 解法二&#xff1a;Floyd 快慢指针法&#xff08;…...

GAN模式奔溃的探讨论文综述(一)

简介 简介:今天带来一篇关于GAN的,对于模式奔溃的一个探讨的一个问题,帮助大家更好的解决训练中遇到的一个难题。 论文题目:An in-depth review and analysis of mode collapse in GAN 期刊:Machine Learning 链接:...