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

【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. 方法一&#xff1a;计算链表长度逻辑流程:代码复杂度分析 1. 题目介绍 题目描述 给你一个链表&#xff0c;删除链表的倒数第 n 个结点&#xff0c;并且返回链表的头结点。 示例 1&#xff1a; 输入&#xff1a;head [1,2,…...

flutter底部导航栏中间按钮凸起,导航栏中间部分凹陷效果

关键代码: Scaffold中设置floatingActionButtonLocation: FloatingActionButtonLocation.centerDocked和extendBody: true&#xff0c; BottomAppBar中设置shape: const CircularNotchedRectangle() Scaffold(extendBody: true,//body是否延伸脚手架底部&#xff0c;在底部导航…...

<项目代码>YOLOv8 红绿灯识别<目标检测>

YOLOv8是一种单阶段&#xff08;one-stage&#xff09;检测算法&#xff0c;它将目标检测问题转化为一个回归问题&#xff0c;能够在一次前向传播过程中同时完成目标的分类和定位任务。相较于两阶段检测算法&#xff08;如Faster R-CNN&#xff09;&#xff0c;YOLOv8具有更高的…...

HTMLHTML5革命:构建现代网页的终极指南 - 4. 使用元素

HTML&HTML5革命&#xff1a;构建现代网页的终极指南 4. 使用元素 大家好&#xff0c;我是莫离老师。 到目前为止&#xff0c;我们已经了解了 HTML 和 HTML5 的基础概念&#xff0c;并且选择了适合自己的开发工具。 今天&#xff0c;我们将迈出实际开发的第一步&#xff0c…...

使用 Selenium 和 Python 爬取腾讯新闻:从基础到实践

使用 Selenium 和 Python 爬取腾讯新闻&#xff1a;从基础到实践 在这篇博客中&#xff0c;我们将介绍如何利用 Selenium 和 Python 爬取腾讯新闻的内容&#xff0c;并将结果保存到 CSV 文件中。本教程包含以下内容&#xff1a; 项目简介依赖安装实现功能的代码实现中的关键技…...

CAD深度清理工具-AVappsDrawingPurge9.0.0(2024.8.27版本) 支持版本CAD2022-2025-供大家学习研究参考

图形文件DWG体积很大&#xff1a;通常没有明显的数据。同时&#xff0c;还其他症状包括&#xff1a; &#xff08;1&#xff09;无法复制和粘贴图元。 &#xff08;2&#xff09;悬挂较长时间选择文本与 “特性”选项板上打开。 &#xff08;3&#xff09;图形文件需要很长时间…...

vue3+vite使用vite-plugin-electron-renderer插件和script-loader插件有冲突

报错信息&#xff1a;Error: Dynamic require of "path" is not supported 报错问题是在使用vite-plugin-electron-renderer插件不支持import动态引入&#xff0c;该报错信息并不准确&#xff0c;实际原因是vite-plugin-electron-renderer插件和script-loader插件有…...

领养我的宠物:SpringBoot开发指南

第2章 开发环境与技术 本章节对开发宠物领养系统需要搭建的开发环境&#xff0c;还有宠物领养系统开发中使用的编程技术等进行阐述。 2.1 Java语言 Java语言是当今为止依然在编程语言行业具有生命力的常青树之一。Java语言最原始的诞生&#xff0c;不仅仅是创造者感觉C语言在编…...

直击高频编程考点:聚焦新版综合编程能力考查汇总

目录 一、业务性编程和广度能力考查 &#xff08;一&#xff09;基本定义 &#xff08;二&#xff09;必要性分析 二、高频考查样题&#xff08;编程扩展问法&#xff09; 考题1: 用java 代码实现一个死锁用例&#xff0c;说说怎么解决死锁问题&#xff1f;&#xff08;高…...

【EI会议征稿 | ACM出版 】第六届计算机信息和大数据应用国际学术会议(CIBDA 2025)

大会官网&#xff1a;www.ic-cibda.org 大会时间&#xff1a;2025年3月14-16日 大会地点&#xff1a;中国-武汉 收录检索&#xff1a;EI Compendex&#xff0c;Scopus 接受/拒稿通知&#xff1a;投稿后约3~8天 大会简介 第六届计算机信息和大数据应用国际学术会议&#xff…...

淘宝商品数据获取:Python爬虫技术的应用与实践

引言 随着电子商务的蓬勃发展&#xff0c;淘宝作为中国最大的电商平台之一&#xff0c;拥有海量的商品数据。这些数据对于市场分析、消费者行为研究、商品推荐系统等领域具有极高的价值。然而&#xff0c;如何高效、合法地从淘宝平台获取这些数据&#xff0c;成为了一个技术挑…...

【C++】getchar() 与 putchar() 的深入解析

博客主页&#xff1a; [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C 文章目录 &#x1f4af;前言&#x1f4af;函数原型及头文件包含&#x1f4af; getchar() 和 putchar() 的基本概念2.1 getchar() 函数2.2 putchar() 函数 &#x1f4af;输入输出的关系与返回值的解释3.1 getchar() …...

Centos7安装MySQL8.0详细教程(压缩包安装方式)

本章教程&#xff0c;主要介绍如何在Centos7上安装MySQL8.0版本数据库&#xff08;压缩包安装方式&#xff09; 一、卸载系统自带的 Mariadb 1、查询 rpm -qa|grep mariadb2.、卸载 如果有查询结果&#xff0c;就进行卸载&#xff0c;没有就跳过该步骤。 rpm -e --nodeps mar…...

深度学习的python基础(1)

一.tensor创建 1.张量的定义 张量在形式上就是多维数组&#xff0c;例如标量就是0维张量&#xff0c;向量就是一维张量&#xff0c;矩阵就是二维张量&#xff0c;而三维张量就可以想象RGB图片&#xff0c;每个channel是一个二维的矩阵&#xff0c;共有三个channel&#xff0…...

拥抱 OpenTelemetry:阿里云 Java Agent 演进实践

作者&#xff1a;陈承 背景 在 2018 年的 2 月&#xff0c;ARMS Java Agent 的第一个版本正式发布&#xff0c;为用户提供无侵入的的可观测数据采集服务。6 年后的今天&#xff0c;随着软件技术的迅猛发展、业务场景的逐渐丰富、用户规模的快速增长&#xff0c;我们逐渐发现过…...

003 MATLAB基础计算

01 方程组的求解 多项式及其运算 多项式在MATLAB中以向量形式存储。 即n次多项式用一个长度为n1的系数向量来表示&#xff0c;且按降幂&#xff0c;缺少的幂次对应的向量元素为0。 多项式的运算主要包括多项式的四则运算、求导、求值和求根运算 多项式的四则运算&#xff1a…...

安卓逆向之Android-Intent介绍

Intent是各个组件之间交互的一种重要方式&#xff0c;它不仅可以指明当前组件想要执行的动作&#xff0c;而且还能在各组件之间传递数据。Intent一般可用于启动Activity、启动Service、发送广播等场景。Intent有多个构造函数的重载。 显式intent 显式 Intent 明确指定要启动的…...

数据库日期时间用什么类型?

数据库中的日期时间类型主要包括DATE、TIME、DATETIME和TIMESTAMP等&#xff0c;它们在存储、格式和范围等方面有所不同。以下是这些类型的详细说明和异同比较&#xff1a; 1. DATE类型 用途&#xff1a;用于存储日期值&#xff0c;不包含时间部分。格式&#xff1a;YYYY-MM-…...

Python中字符串和正则表达式

Python中字符串和正则表达式 在Python编程中&#xff0c;字符串是最常用的数据类型之一。字符串用于表示文本数据&#xff0c;而正则表达式则是一种强大的工具&#xff0c;用于处理和匹配字符串中的模式。本文将介绍Python中的字符串操作、字符串格式化以及如何使用正则表达式…...

Leecode刷题C语言之N皇后

执行结果:通过 执行用时和内存消耗如下&#xff1a; 代码如下&#xff1a; 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))…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

基于SpringBoot在线拍卖系统的设计和实现

摘 要 随着社会的发展&#xff0c;社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统&#xff0c;主要的模块包括管理员&#xff1b;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...

解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist

现象&#xff1a; android studio报错&#xff1a; [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决&#xff1a; 不要动CMakeLists.…...

STM32---外部32.768K晶振(LSE)无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...