当前位置: 首页 > 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))…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

Typeerror: cannot read properties of undefined (reading ‘XXX‘)

最近需要在离线机器上运行软件&#xff0c;所以得把软件用docker打包起来&#xff0c;大部分功能都没问题&#xff0c;出了一个奇怪的事情。同样的代码&#xff0c;在本机上用vscode可以运行起来&#xff0c;但是打包之后在docker里出现了问题。使用的是dialog组件&#xff0c;…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...