【Leetcode】19. 删除链表的第N个节点
【Leetcode】19. 删除链表的第N个节点
- 1. 题目介绍
- 2. 方法一:计算链表长度
- 逻辑流程:
- 代码
- 复杂度分析
1. 题目介绍
题目描述
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
示例 1:
- 输入:head = [1,2,3,4,5], n = 2
- 输出:[1,2,3,5]
示例 2:
- 输入:head = [1], n = 1
- 输出:[]
示例 3:
- 输入:head = [1,2], n = 1
- 输出:[1]
提示
- 链表中结点的数目为 sz
- 1 <= sz <= 30
- 0 <= Node.val <= 100
- 1 <= n <= sz
2. 方法一:计算链表长度
逻辑流程:
- 输入是一个链表
1 -> 2 -> 3 -> 4 -> None
- 创建一个虚拟头结点 dummy,它的 next 指向链表的实际头结点 head。
这一步是为了处理边缘情况,比如当要删除的是头节点时,可以避免额外的条件判断。
dummy -> 1 -> 2 -> 3 -> 4 -> None
其中 dummy 是一个虚拟头结点,它的 next 指向实际的头结点 1。
- 调用辅助函数 getLength 来计算整个链表的长度。
- 初始化一个指针 cur,指向 dummy。
这个指针将用来遍历链表,直到找到待删除节点的前一个节点。
如果执行了 ListNode cur = dummy;,那么 cur 也指向 dummy 所指向的那个节点。
此时,cur 和 dummy 的关系如下:
dummy (cur) -> 1 -> 2 -> 3 -> 4 -> None
- 使用一个循环,使 cur 向后移动 length - n + 1 次,这样 cur 就会停在待删除节点的前一个位置。
如果执行 cur = cur.next;,cur 将移动到下一个节点 1:
dummy (cur)↓1 -> 2 -> 3 -> 4 -> None
- 更新 cur.next 为 cur.next.next,跳过当前的下一个节点(即待删除节点)。
如果执行 cur.next = cur.next.next;,这将跳过节点 2,并让 1 直接指向 3:
dummy (cur)↓1 -> 3 -> 4 -> None| / |2 \ |\ |\ |4
- 最后,返回 dummy.next 作为新的头节点,这是因为如果删除了原始的头节点,那么新的头节点就是 dummy.next。
在这个过程中,dummy 的 next 指针也被更新了,因为 cur 和 dummy 指向同一个节点。所以,dummy 的 next 也从 1 变成了 3。
代码
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0, head);int length = getLength(head);ListNode cur = dummy;for (int i = 1; i < length - n + 1; ++i) {cur = cur.next;}cur.next = cur.next.next;ListNode ans = dummy.next;return ans;}public int getLength(ListNode head) {int length = 0;while (head != null) {++length;head = head.next;}return length;}
}
复杂度分析
-
时间复杂度:O(L),其中 L 是链表的长度。
-
空间复杂度:O(1)。
相关文章:
【Leetcode】19. 删除链表的第N个节点
【Leetcode】19. 删除链表的第N个节点 1. 题目介绍2. 方法一:计算链表长度逻辑流程:代码复杂度分析 1. 题目介绍 题目描述 给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 示例 1: 输入:head [1,2,…...
flutter底部导航栏中间按钮凸起,导航栏中间部分凹陷效果
关键代码: Scaffold中设置floatingActionButtonLocation: FloatingActionButtonLocation.centerDocked和extendBody: true, BottomAppBar中设置shape: const CircularNotchedRectangle() Scaffold(extendBody: true,//body是否延伸脚手架底部,在底部导航…...
<项目代码>YOLOv8 红绿灯识别<目标检测>
YOLOv8是一种单阶段(one-stage)检测算法,它将目标检测问题转化为一个回归问题,能够在一次前向传播过程中同时完成目标的分类和定位任务。相较于两阶段检测算法(如Faster R-CNN),YOLOv8具有更高的…...
HTMLHTML5革命:构建现代网页的终极指南 - 4. 使用元素
HTML&HTML5革命:构建现代网页的终极指南 4. 使用元素 大家好,我是莫离老师。 到目前为止,我们已经了解了 HTML 和 HTML5 的基础概念,并且选择了适合自己的开发工具。 今天,我们将迈出实际开发的第一步,…...
使用 Selenium 和 Python 爬取腾讯新闻:从基础到实践
使用 Selenium 和 Python 爬取腾讯新闻:从基础到实践 在这篇博客中,我们将介绍如何利用 Selenium 和 Python 爬取腾讯新闻的内容,并将结果保存到 CSV 文件中。本教程包含以下内容: 项目简介依赖安装实现功能的代码实现中的关键技…...
CAD深度清理工具-AVappsDrawingPurge9.0.0(2024.8.27版本) 支持版本CAD2022-2025-供大家学习研究参考
图形文件DWG体积很大:通常没有明显的数据。同时,还其他症状包括: (1)无法复制和粘贴图元。 (2)悬挂较长时间选择文本与 “特性”选项板上打开。 (3)图形文件需要很长时间…...
vue3+vite使用vite-plugin-electron-renderer插件和script-loader插件有冲突
报错信息:Error: Dynamic require of "path" is not supported 报错问题是在使用vite-plugin-electron-renderer插件不支持import动态引入,该报错信息并不准确,实际原因是vite-plugin-electron-renderer插件和script-loader插件有…...
领养我的宠物:SpringBoot开发指南
第2章 开发环境与技术 本章节对开发宠物领养系统需要搭建的开发环境,还有宠物领养系统开发中使用的编程技术等进行阐述。 2.1 Java语言 Java语言是当今为止依然在编程语言行业具有生命力的常青树之一。Java语言最原始的诞生,不仅仅是创造者感觉C语言在编…...
直击高频编程考点:聚焦新版综合编程能力考查汇总
目录 一、业务性编程和广度能力考查 (一)基本定义 (二)必要性分析 二、高频考查样题(编程扩展问法) 考题1: 用java 代码实现一个死锁用例,说说怎么解决死锁问题?(高…...
【EI会议征稿 | ACM出版 】第六届计算机信息和大数据应用国际学术会议(CIBDA 2025)
大会官网:www.ic-cibda.org 大会时间:2025年3月14-16日 大会地点:中国-武汉 收录检索:EI Compendex,Scopus 接受/拒稿通知:投稿后约3~8天 大会简介 第六届计算机信息和大数据应用国际学术会议ÿ…...
淘宝商品数据获取:Python爬虫技术的应用与实践
引言 随着电子商务的蓬勃发展,淘宝作为中国最大的电商平台之一,拥有海量的商品数据。这些数据对于市场分析、消费者行为研究、商品推荐系统等领域具有极高的价值。然而,如何高效、合法地从淘宝平台获取这些数据,成为了一个技术挑…...
【C++】getchar() 与 putchar() 的深入解析
博客主页: [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C 文章目录 💯前言💯函数原型及头文件包含💯 getchar() 和 putchar() 的基本概念2.1 getchar() 函数2.2 putchar() 函数 💯输入输出的关系与返回值的解释3.1 getchar() …...
Centos7安装MySQL8.0详细教程(压缩包安装方式)
本章教程,主要介绍如何在Centos7上安装MySQL8.0版本数据库(压缩包安装方式) 一、卸载系统自带的 Mariadb 1、查询 rpm -qa|grep mariadb2.、卸载 如果有查询结果,就进行卸载,没有就跳过该步骤。 rpm -e --nodeps mar…...
深度学习的python基础(1)
一.tensor创建 1.张量的定义 张量在形式上就是多维数组,例如标量就是0维张量,向量就是一维张量,矩阵就是二维张量,而三维张量就可以想象RGB图片,每个channel是一个二维的矩阵,共有三个channel࿰…...
拥抱 OpenTelemetry:阿里云 Java Agent 演进实践
作者:陈承 背景 在 2018 年的 2 月,ARMS Java Agent 的第一个版本正式发布,为用户提供无侵入的的可观测数据采集服务。6 年后的今天,随着软件技术的迅猛发展、业务场景的逐渐丰富、用户规模的快速增长,我们逐渐发现过…...
003 MATLAB基础计算
01 方程组的求解 多项式及其运算 多项式在MATLAB中以向量形式存储。 即n次多项式用一个长度为n1的系数向量来表示,且按降幂,缺少的幂次对应的向量元素为0。 多项式的运算主要包括多项式的四则运算、求导、求值和求根运算 多项式的四则运算:…...
安卓逆向之Android-Intent介绍
Intent是各个组件之间交互的一种重要方式,它不仅可以指明当前组件想要执行的动作,而且还能在各组件之间传递数据。Intent一般可用于启动Activity、启动Service、发送广播等场景。Intent有多个构造函数的重载。 显式intent 显式 Intent 明确指定要启动的…...
数据库日期时间用什么类型?
数据库中的日期时间类型主要包括DATE、TIME、DATETIME和TIMESTAMP等,它们在存储、格式和范围等方面有所不同。以下是这些类型的详细说明和异同比较: 1. DATE类型 用途:用于存储日期值,不包含时间部分。格式:YYYY-MM-…...
Python中字符串和正则表达式
Python中字符串和正则表达式 在Python编程中,字符串是最常用的数据类型之一。字符串用于表示文本数据,而正则表达式则是一种强大的工具,用于处理和匹配字符串中的模式。本文将介绍Python中的字符串操作、字符串格式化以及如何使用正则表达式…...
Leecode刷题C语言之N皇后
执行结果:通过 执行用时和内存消耗如下: 代码如下: int solutionsSize;char** generateBoard(int* queens, int n) {char** board (char**)malloc(sizeof(char*) * n);for (int i 0; i < n; i) {board[i] (char*)malloc(sizeof(char) * (n 1))…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
【杂谈】-递归进化:人工智能的自我改进与监管挑战
递归进化:人工智能的自我改进与监管挑战 文章目录 递归进化:人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管?3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...
【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密
在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...
《Playwright:微软的自动化测试工具详解》
Playwright 简介:声明内容来自网络,将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具,支持 Chrome、Firefox、Safari 等主流浏览器,提供多语言 API(Python、JavaScript、Java、.NET)。它的特点包括&a…...
(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...
Python爬虫实战:研究feedparser库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中,新增了一个本地验证码接口 /code,使用函数式路由(RouterFunction)和 Hutool 的 Circle…...
初学 pytest 记录
安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...
