LeetCode_19_中等_删除链表的倒数第N个结点
文章目录
- 1. 题目
- 2. 思路及代码实现(Python)
- 2.1 计算链表长度
- 2.2 栈
1. 题目
给你一个链表,删除链表的倒数第 n n n 个结点,并且返回链表的头结点。
示例 1:
输入: h e a d = [ 1 , 2 , 3 , 4 , 5 ] , n = 2 head = [1,2,3,4,5], n = 2 head=[1,2,3,4,5],n=2
输出: [ 1 , 2 , 3 , 5 ] [1,2,3,5] [1,2,3,5]
示例 2:
输入: h e a d = [ 1 ] , n = 1 head = [1], n = 1 head=[1],n=1
输出: [ ] [ ] []
示例 3:
输入: h e a d = [ 1 , 2 ] , n = 1 head = [1,2], n = 1 head=[1,2],n=1
输出: [ 1 ] [1] [1]
提示:
- 1 < = s z < = 30 1 <= sz <= 30 1<=sz<=30,其中 s z sz sz 为链表中的节点数目
- 0 < = N o d e . v a l < = 100 0 <= Node.val <= 100 0<=Node.val<=100
- 1 < = n < = s z 1 <= n <= sz 1<=n<=sz
2. 思路及代码实现(Python)
在对链表进行操作时,一种常用的技巧是添加一个哑节点(dummy node),它的 next \textit{next} next 指针指向链表的头节点。这样一来,就不需要对头节点进行特殊的判断了。
例如,在本题中,如果我们要删除节点 y y y,我们需要知道节点 y y y 的前驱节点 x x x,并将 x x x 的指针指向 y y y 的后继节点。但由于头节点不存在前驱节点,因此我们需要在删除头节点时进行特殊判断。但如果我们添加了哑节点,那么头节点的前驱节点就是哑节点本身,此时我们就只需要考虑通用的情况即可。
题解引用来源:力扣官方题解
2.1 计算链表长度
一种容易想到的方法是,我们首先从头节点开始对链表进行一次遍历,得到链表的长度 L L L。随后我们再从头节点开始对链表进行一次遍历,当遍历到第 L − n + 1 L−n+1 L−n+1 个节点时,它就是我们需要删除的节点。
为了方便删除操作,我们可以从哑节点开始遍历 L − n + 1 L−n+1 L−n+1 个节点。当遍历到第 L − n + 1 L−n+1 L−n+1 个节点时,它的下一个节点就是我们需要删除的节点,这样我们只需要修改一次指针,就能完成删除操作。

该算法的时间复杂度为 O ( L ) O(L) O(L),其中, L L L 是链表的长度;空间复杂度为 O ( 1 ) O(1) O(1)。
class Solution:def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:def getLength(head: ListNode) -> int:length = 0while head:length += 1head = head.nextreturn lengthdummy = ListNode(0, head)length = getLength(head)cur = dummyfor i in range(1, length - n + 1):cur = cur.nextcur.next = cur.next.nextreturn dummy.next
执行用时:44 ms
消耗内存:16.45 MB
2.2 栈
我们也可以在遍历链表的同时将所有节点依次入栈。根据栈「先进后出」的原则,我们弹出栈的第 n n n 个节点就是需要删除的节点,并且目前栈顶的节点就是待删除节点的前驱节点。这样一来,删除操作就变得十分方便了。
上一个方法用链表结构,存储每个节点的指向节点,因此节省存储空间,无需存储所有的节点。而用栈的方法,在Python中用元素带顺序的列表来表征进出操作,实现逻辑很直观简单,但需牺牲部分存储空间。
该算法的时间复杂度为 O ( L ) O(L) O(L),空间复杂度也为 O ( L ) O(L) O(L)。
class Solution:def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:dummy = ListNode(0, head)stack = list()cur = dummywhile cur:stack.append(cur)cur = cur.nextfor i in range(n):stack.pop()prev = stack[-1]prev.next = prev.next.nextreturn dummy.next
执行用时:27 ms
消耗内存:16.38 MB
相关文章:
LeetCode_19_中等_删除链表的倒数第N个结点
文章目录 1. 题目2. 思路及代码实现(Python)2.1 计算链表长度2.2 栈 1. 题目 给你一个链表,删除链表的倒数第 n n n 个结点,并且返回链表的头结点。 示例 1: 输入: h e a d [ 1 , 2 , 3 , 4 , 5 ] , n…...
C++泛编程(3)
类模板基础 1.类模板的基本概念2.类模板的分文件编写3.类模板的嵌套 (未完待续...) 在往节内容中,我们详细介绍了函数模板,这节开始我们就来聊一聊类模板。C中,类的细节远比函数多,所以这个专题也会更复杂。…...
python基于django的公交线路查询系统mf383
1.个人信息的管理:对用户名,密码的增加、删除等 2.线路信息的管理:对线路的增加、修改、删除等 3.站点信息的管理:对站点的增加、修改、删除等 4.车次信息的管理:对车次的增加、修改、删除等 5.线路查询、站点查询 …...
ElementUI 组件:Container 布局容器实例
ElementUI安装与使用指南 Container 布局容器 点击下载learnelementuispringboot项目源码 效果图 el-container-example.vue(Container 布局容器实例)页面效果图 项目里el-container-example.vue代码 <script> export default {name: el_cont…...
【数据结构 09】哈希
哈希算法:哈希也叫散列、映射,将任意长度的输入通过散列运算转化为固定长度的输出,该输出就是哈希值(散列值)。 哈希映射是一种压缩映射,通常情况下,散列值的空间远小于输入值的空间。 哈希运…...
理解和管理Linux文件权限
理解和管理Linux文件权限 文件权限的基本概念和表示方式 文件权限管理在Linux系统中是非常重要的,它决定了谁可以访问、读取、写入或执行文件。文件权限以及所有者、所属组等属性可以通过 ls -l 命令查看。 在 ls -l 命令的输出中,文件的权限通常表示…...
爬虫(二)
1.同步获取短视频 1.只要播放地址对Json数据解析,先把列表找出: 2.只想要所有的播放地址,通过列表表达式循环遍历这个列表拿到每个对象,再从一个个对象里面找到Video,再从Video里面找到播放地址(play_addr),再从播放地址找到播放…...
Flink实战四_TableAPISQL
接上文:Flink实战三_时间语义 1、Table API和SQL是什么? 接下来理解下Flink的整个客户端API体系,Flink为流式/批量处理应用程序提供了不同级别的抽象: 这四层API是一个依次向上支撑的关系。 Flink API 最底层的抽象就是有状态实…...
海外云手机开辟企业跨境电商新道路
近几年,海外云手机为跨境电商、海外媒体引流、游戏行业等互联网领域注入了蓬勃活力。对于国内跨境电商而言,在亚马逊及其他平台上,短视频引流和社交电商营销成为最为有效的流量来源。如何通过海外云手机的助力,在新兴社交平台为企…...
【51单片机系列】中断优先级介绍及使用
文章来源:《51单片机原理及应用(第3版)》5.4节。 51单片机采用了自然优先级和人工设置高、低优先级的策略。 当CPU处理低优先级中断,又发生更高级中断时,此时中断处理过程如下图所示。 一个正在执行的低优先级中断服…...
.net core 6 集成 elasticsearch 并 使用分词器
1、nuget包安装NEST、安装elasticsearch、kibana、ik分词器、拼音分词器 2、创建操作对象 //索引库 static string indexName "testparticper"; //es 操作对象 ElasticClient elasticClient new ElasticClient(new ConnectionSettings(new Uri("http://192.…...
Unity项目从built-in升级到URP(包含早期版本和2023版本)
unity不同版本的升级URP的方式不一样,但是大体流程是相似的 首先是加载URP包 Windows -> package manager,在unity registry中找到Universal RP 2023版本: 更早的版本: 创建URP资源和渲染器 有些版本在加载时会自动创建&#…...
2月4号作业
编写程序实现二叉树的创建,三种遍历自己销毁 #include <myhead.h>#define TRUE 1 #define FALSE 0 #define OVERFLOW -2 #define OK 1 #define ERROR 0#define INIT_SIZE 20 #define INCREMENT_SIZE 5typedef int Status; typedef int TElemType; //存储结构…...
瑞_23种设计模式_建造者模式
文章目录 1 建造者模式(Builder Pattern)1.1 介绍1.2 概述1.3 创作者模式的结构 2 案例一2.1 需求2.2 代码实现 3 案例二3.1 需求3.2 代码实现 4 模式拓展 ★★★4.1 重构前4.2 重构后 5 总结5.1 建造者模式优缺点5.2 建造者模式使用场景5.3 建造者模式 …...
GA/T 1707-2019 防爆安全门检测
防爆安全门是指能抵抗爆炸冲击波作用的特种防护门,根据防爆门的防爆性能的不同,分为非接触爆炸防爆门和防接触爆炸防爆门,根据防爆能力的不同,分为不同等级。 GA/T 1707-2019 防爆安全门检测项目 测试项目 测试标准 外观质量 …...
k8s学习-数据管理
在Docker中我们知道,要想实现数据的持久化(所谓Docker的数据持久化即数据不随着Container的结束而结束),需要将数据从宿主机挂载到容器中,常用的手段就是Volume数据卷。在K8S中,也提供了存储模型Volume&…...
java hutool工具类实现将数据下载到excel
通过hutool工具类,对于excel的操作变得非常简单,上篇介绍的是excel的上传,对excel的操作,核心代码只有一行。本篇的excel的下载,核心数据也不超过两行,简洁方便,特别适合当下的低代码操作。 下载…...
【C/Python】Gtk部件ListStore的使用
一、C语言 在GTK中,Gtk.ListStore是一个实现了Gtk.TreeModel接口的存储模型,用于在如Gtk.TreeView这样的控件中存储数据。以下是一个简单的使用Gtk.ListStore的C语言示例,该示例创建了一个列表,并在图形界面中显示: …...
Swift 入门之自定义类型的模式匹配(Pattern Matching)
概览 小伙伴们都知道 Swift 是一门简洁、类型安全、极富表现力以及“性感迷人”的编程语言。 和大多数语言一样,在 Swift 中也有一些隐藏着的、不为人知的宝藏特性。利用它们我们可以极大增加撸码的愉悦和成就感。 其中,模式匹配(Pattern …...
MySQL-----DML基础操作
DML语句 DML英文全称是Data Manipulation Language(数据操作语言),用来对数据库中表的数据记录进行增删改操作。 ▶ 添加数据(INSERT) 【语法】 1. 给指定字段添加数据 INSERTO 表名 (字段名1,字段名2,...) VALUES (值1,值2,...); 2.给全…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...
python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...
深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
【2025年】解决Burpsuite抓不到https包的问题
环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...
前端开发面试题总结-JavaScript篇(一)
文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包(Closure)?闭包有什么应用场景和潜在问题?2.解释 JavaScript 的作用域链(Scope Chain) 二、原型与继承3.原型链是什么?如何实现继承&a…...
用docker来安装部署freeswitch记录
今天刚才测试一个callcenter的项目,所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...
