动图:删除链表的倒数第 N 个结点（删除链表中值为x的结点）
ztj100 2024-11-07 13:40 34 浏览 0 评论
19. 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗?
解题思路
在链表中要删除某个节点 nodeB，必须先找到 该节点的前一节点 nodeA ，再将 nodeA 指向 nodeB 的下一节点 nodeC ，从而实现节点 nodeB 的删除。
例如要删除链表 L(1->2->3->4->5) 中 值为 3 的节点，首先得找到该节点的前一节点（值为 2 的节点），才能实现该节点的删除，如下图示：
题目要求删除 倒数第 n 个 节点，所以首先得找到 该节点的前一节点 ，但由于不知道 整个链表的长度，因此不知道 待删除的节点是正数的第几个节点，所以很难从头节点开始遍历时删除掉这个节点。
思路一
先遍历一遍链表，获取整个链表的长度；假设整个链表的长度为 l，则可知要删除的节点为第 l - n + 1 个节点；再遍历一遍，删除倒数第 n 个节点。例如链表 L 为 1->2->3->4->5，n = 3，则要删除的节点为 第 5 - 3 + 1 = 3 个节点 。
思路二
尽管思路一可行，但是需要 遍历链表两遍，不够简洁，而且题目的 进阶 中也提到尝试使用一趟扫描实现，因此本文采用 双指针 的策略，实现通过一次扫描删除 倒数第 n 个节点 。
在上一期链表相关专题 虚拟头节点秒杀链表问题 中提到 增加虚拟头节点 的策略解决链表问题，增加虚拟头节点的 好处 在于：不需要单独考虑头节点，这样对头节点的处理就像跟其它节点一样。本文也同样采用这种策略。
举栗
以链表 1->2->3->4->5，n = 3 为栗，如下如示。
按照上面分析，先要找到 倒数第 3 个节点的前一节点，即值为 2 的节点；
增加虚拟头节点
值为 2 的节点是 倒数第 4 个节点（后往前数），增加两指针 fast/slow，分别指向最后一个元素（NULL）和上图中 target 的位置；
此时 fast 跟 slow 之间的间距是固定（n = 3）的，找到 target(slow)后，只需要删除其下一节点即可，但 slow 指向的节点前面有多少个节点该如何确定呢？
由于当前已知 fast 和 slow 指向节点之间的长度是固定的，只需要将这两个指针向前挪，直到 slow 挪到虚拟头节点（值为 0）的位置，此时 fast 指向值为 4 的节点的位置，fast 只需要由虚拟头节点的位置 右移 n + 1 = 4 即可。如下图示：
当 fast 右移至值为 4 的节点时，指针 slow 和 fast 同时右移，直至 fast 移到 NULL，此时 slow 刚好到 target 位置，即指向 倒数第 n + 1 个节点，如下图示。
Show me the Code
相关推荐
- Python 操作excel的坑__真实的行和列
-
大佬给的建议__如何快速处理excelopenpyxl库操作excel的时候，单个表的数据量大一些处理速度还能接受，如果涉及多个表甚至多个excel文件的时候速度会很慢，还是建议用pandas来处理，...
- Python os.path模块使用指南:轻松处理文件路径
-
前言在Python编程中，文件和目录的操作是非常重要的一部分。为了方便用户进行文件和目录的操作，Python标准库提供了os模块。其中，os.path子模块提供了一些处理文件路径的函数和方法。本文主要...
- Python常用内置模块介绍——文件与系统操作详解
-
Python提供了多个强大的内置模块用于文件和系统操作，下面我将详细介绍最常用的几个模块及其核心功能。1.os模块-操作系统交互...
- Python Flask 建站框架实操教程（flask框架网页）
-
下面我将带您从零开始构建一个完整的Flask网站，包含用户认证、数据库操作和前端模板等核心功能。##第一部分：基础项目搭建###1.创建项目环境```bash...
- 为你的python程序上锁:软件序列号生成器
-
序列号很多同学可能开发了非常多的程序了，并且进行了...
- PO设计模式全攻略，在 UI 自动化中的实践总结(以企业微信为例)
-
一、什么是PO设计模式？PO（PageObject）设计模式将某个页面的所有元素对象定位和对元素对象的操作封装成一个Page类，即一个py文件，并以页面为单位来写测试用例，实现页面对象和测试用例的...
- 这种小工具居然也能在某鱼卖钱?我用Python一天能写...
-
前两天在某鱼闲逛，本来想找个二手机械键盘，结果刷着刷着突然看到有人在卖——Word批量转PDF小工具...
- python打包成exe，程序有图标，但是任务栏和窗口都没有显示图标
-
代码中指定图标信息#设置应用ID，确保任务栏图标正确显示ifsys.platform=="win32":importctypesapp_id=...
- 使用Python构建电影推荐系统（用python做推荐系统）
-
在日常数据挖掘工作中，除了会涉及到使用Python处理分类或预测任务，有时候还会涉及推荐系统相关任务。...
- python爬取并分析淘宝商品信息（python爬取淘宝商品数据）
-
python爬取并分析淘宝商品信息背景介绍一、模拟登陆二、爬取商品信息1.定义相关参数2.分析并定义正则3.数据爬取三、简单数据分析1.导入库2.中文显示3.读取数据4.分析价格分布5.分析销售...
- OpenCV入门学习基础教程(从小白变大神)
-
Opencv是用于快速处理图像处理、计算机视觉问题的工具,支持多种语言进行开发如c++、python、java等,下面这篇文章主要给大家介绍了关于openCV入门学习基础教程的相关资料,需要的朋友可以...
- python图像处理-一行代码实现灰度图抠图
-
抠图是ps的最基本技能，利用python可以实现用一行代码实现灰度图抠图。基础算法是...
- 从头开始学python:如何用Matplotlib绘图表
-
Matplotlib是一个用于绘制图表的库。如果你有用过python处理数据，那Matplotlib可以更直观的帮你把数据展示出来。直接上代码看例子：importmatplotlib.pyplot...
- Python爬取爱奇艺腾讯视频 250,000 条数据分析为什么李诞不值得了
-
在《Python爬取爱奇艺52432条数据分析谁才是《奇葩说》的焦点人物？》这篇文章中，我们从爱奇艺爬取了5万多条评论数据，并对一些关键数据进行了分析，由此总结出了一些明面上看不到的数据，并...
- Python Matplotlib 库使用基本指南
-
简介Matplotlib是一个广泛使用的Python数据可视化库，它可以创建各种类型的图表、图形和可视化效果。无论是简单的折线图还是复杂的热力图，Matplotlib提供了丰富的功能来满足我们...
欢迎 你 发表评论:
- 一周热门
- 最近发表
-
- Python 操作excel的坑__真实的行和列
- Python os.path模块使用指南:轻松处理文件路径
- Python常用内置模块介绍——文件与系统操作详解
- Python Flask 建站框架实操教程（flask框架网页）
- 为你的python程序上锁:软件序列号生成器
- PO设计模式全攻略，在 UI 自动化中的实践总结(以企业微信为例)
- 这种小工具居然也能在某鱼卖钱?我用Python一天能写...
- python打包成exe，程序有图标，但是任务栏和窗口都没有显示图标
- 使用Python构建电影推荐系统（用python做推荐系统）
- python爬取并分析淘宝商品信息（python爬取淘宝商品数据）
- 标签列表
-
- idea eval reset (50)
- vue dispatch (70)
- update canceled (42)
- order by asc (53)
- spring gateway (67)
- 简单代码编程 贪吃蛇 (40)
- transforms.resize (33)
- redisson trylock (35)
- 卸载node (35)
- np.reshape (33)
- torch.arange (34)
- npm 源 (35)
- vue3 deep (35)
- win10 ssh (35)
- vue foreach (34)
- idea设置编码为utf8 (35)
- vue 数组添加元素 (34)
- std find (34)
- tablefield注解用途 (35)
- python str转json (34)
- java websocket客户端 (34)
- tensor.view (34)
- java jackson (34)
- vmware17pro最新密钥 (34)
- mysql单表最大数据量 (35)