【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))…...
Python爬虫实战:研究MechanicalSoup库相关技术
一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...
【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...
label-studio的使用教程(导入本地路径)
文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
ip子接口配置及删除
配置永久生效的子接口,2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...
