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

Leetcode 删除链表倒数第 N 个节点

算法思想:

使用了双指针法。下面是详细的算法思想:

1. 引入虚拟头节点(dummy node)

  • 为了处理链表的一些边界情况(比如删除头节点),我们在链表的头部引入了一个虚拟节点 dummy,并让它指向原来的头节点 head。这样,无论我们要删除哪个节点,处理过程都变得更加统一和简单。

2. 定义两个指针:快指针(fast)和慢指针(slow)

  • 我们使用两个指针,fastslow,最初都指向虚拟头节点 dummy
  • 快指针 fast 会比慢指针 slow 超前移动 n+1 步。这样,当 fast 指向链表末尾(null)时,slow 刚好指向要删除节点的前一个节点。

3. 移动快指针

  • 首先,快指针 fast 先向前移动 n+1 步,这样可以确保快指针和慢指针之间相隔 n 个节点。

4. 同时移动快慢指针

  • 接下来,快慢指针一起向前移动,直到快指针到达链表的末尾。这时,慢指针 slow 就刚好处于要删除节点的前一个位置。

5. 删除节点

  • 现在,慢指针 slow 的下一个节点就是我们需要删除的节点。通过 slow.next = slow.next.next,我们跳过了这个节点,达到了删除的目的。

6. 返回新的头节点

  • 最后,返回 dummy.next。注意,链表的头节点可能发生了变化(如果原来的头节点被删除),因此我们返回虚拟节点 dummy 的下一个节点作为新的链表头节点。

代码核心思路总结:

  • 通过快慢指针法,仅需遍历链表一次(一次循环)就可以找到倒数第N个节点,并将其删除,时间复杂度为 O(L),其中 L 是链表的长度。空间复杂度为 O(1),因为只用了常数级别的额外空间。

示例分析:

假设输入链表为 [1, 2, 3, 4, 5]n = 2,即删除倒数第二个节点。

  1. 初始化fastslow 都指向虚拟节点 dummy
  2. 快指针前移fast 先向前移动 n+1 = 3 步,指向节点 3
  3. 同步移动:同时移动 fastslow,直到 fast 指向 null,此时 slow 指向节点 3 的前一个节点,即节点 2
  4. 删除节点:通过 slow.next = slow.next.next 删除节点 4,最终链表变为 [1, 2, 3, 5]

这样就成功地删除了倒数第2个节点。

在这里插入图片描述
java 实现代码:

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummyNode = new ListNode(0);dummyNode.next = head;ListNode slow = dummyNode; //dummyNode,slow,fast都是引用类型ListNode fast = dummyNode;for(int i = 0; i <= n; i++) { //快指针先移动 n+1 步fast = fast.next;}while(fast != null) { //然后快慢指针一起移动slow = slow.next;fast = fast.next;}slow.next = slow.next.next;return dummyNode.next;}
}

相关文章:

Leetcode 删除链表倒数第 N 个节点

算法思想&#xff1a; 使用了双指针法。下面是详细的算法思想&#xff1a; 1. 引入虚拟头节点&#xff08;dummy node&#xff09; 为了处理链表的一些边界情况&#xff08;比如删除头节点&#xff09;&#xff0c;我们在链表的头部引入了一个虚拟节点 dummy&#xff0c;并让…...

[移植] tgi 编译

这里写自定义目录标题 报错 报错 Collecting numpy1.26.4 (from -r requirements_cuda.txt (line 21))Downloading numpy-1.26.4.tar.gz (15.8 MB)━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 15.8/15.8 MB 15.0 MB/s eta 0:00:00Inst…...

vue-element-admin后台集成方案

文章目录 vue-element-admin后台集成方案介绍使用安装目录介绍 vue-element-admin后台集成方案 介绍 官方网站 https://panjiachen.github.io/vue-element-admin-site/zh/guide/#%E5%8A%9F%E8%83%BD使用 安装 这里有三个模板&#xff0c;我们一般选择基础模板进行开发就好…...

40条经典ChatGPT论文指令,圈定选题和进行论文构思

目录 1、用ChatGPT圈定选题范围2、用ChatGPT生成研究方法和思路3、用ChatGPT扩展论文观点和论证4、用ChatGPT辅助论文结构设计5、如何直接使用ChatGPT4o、o1、OpenAI Canvas6、OpenAI Canvas增强了啥&#xff1f;7、编程功能增强 &#x1f447; ChatGPT o1网页入口在文末&#…...

在不支持WSL2的Windows环境下安装Redis并添加环境变量的方法

如果系统版本支持 WSL 2 可跳过本教程。使用官网提供的教程即可 官网教程 查看是否支持 WSL 2 如果不支持或者觉得麻烦可以按照下面的方式安装 下载 点击打开下载地址 下载 zip 文件即可 安装 将下载的 zip 文件解压到自己想要解压的地方即可。&#xff08;注意&#x…...

《Electron 基础知识》代码打开开发者工具DevTools

初始化 const mainWindow new BrowserWindow({width: 1400,height: 800 );打开 接口 openDevTools mainWindow.webContents.openDevTools();关闭 接口 closeDevTools mainWindow.webContents.closeDevTools();...

小米R3G刷机OP

小米R3G刷机OP 22年购买了一个小米R3G路由器&#xff0c;刷OP系统后可以中继校园网&#xff0c;从而让智能开关、小爱同学可以联网。 当年的价格还是55元&#xff0c;现在只需要30元了&#xff0c;价格越来越便宜&#xff0c;并且OP版本越来越完善了。 之前刷机过breed系统&…...

移动机器人规划控制合集

系列文章目录 提示&#xff1a;这里可以添加系列文章的所有文章的目录&#xff0c;目录需要自己手动添加 TODO:写完再整理 文章目录 系列文章目录前言 前言 认知有限&#xff0c;望大家多多包涵&#xff0c;有什么问题也希望能够与大家多交流&#xff0c;共同成长&#xff01;…...

Type-C接口桌面显示器的优势

随着科技的飞速发展&#xff0c;电子设备的连接性、便捷性和高效性成为了消费者关注的重点。在这个背景下&#xff0c;Type-C接口桌面显示器以其卓越的性能和广泛的兼容性&#xff0c;正逐步成为市场上的主流选择。本文将深入探讨Type-C接口桌面显示器的优势、应用场景、市场现…...

机器学习中的熵(Entropy)是什么?

在机器学习和信息理论中&#xff0c;熵&#xff08;Entropy&#xff09;是衡量不确定性和信息量的一个重要概念。熵最初由信息论的奠基人克劳德香农&#xff08;Claude Shannon&#xff09;在1948年提出&#xff0c;用来衡量信息源的信息不确定性。在机器学习中&#xff0c;熵被…...

JAVA基础:Lock不同的锁形式

1.1 可重入锁 synchronized就是一个可重入锁 使用lock时&#xff0c;常用的ReentryLock就是可重入锁 当一个线程在获得a对象锁之后&#xff0c;可以继续重复获得对象锁 代码形式就是 线程调用同步代码段&#xff0c;在没有执行完毕前&#xff0c;又调用了该对象的另一个同步…...

【LeetCode每日一题】——679.24 点游戏

文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时间频度】九【代码实现】十【提交结果】 一【题目类别】 回溯 二【题目难度】 困难 三【题目编号】 679.24 点游戏 四【题目描述】 给定一个长度为4…...

【Conda】Conda命令详解:高效更新与环境管理指南

目录 1. Conda 更新命令1.1 更新 Conda 核心1.2 更新所有包 2. 严格频道优先级3. 强制安装特定版本4. 创建与管理环境4.1 创建新环境4.2 激活和停用环境4.3 导出和导入环境4.4 删除环境 5. 清理缓存总结 Conda 是一个强大的包管理和环境管理工具&#xff0c;广泛应用于数据科学…...

机器学习:回归模型和分类模型的评估方法介绍

回归模型和分类模型评估方法详解 一、回归模型评估方法 &#xff08;一&#xff09;均方误差&#xff08;MSE&#xff09; 原理 均方误差是衡量回归模型预测值与真实值之间平均平方差的指标。它通过计算预测值与真实值之差的平方的平均值来评估模型的性能。其数学公式为&…...

担心学术窃取?阿里云加密的AI论文工具帮你锁紧数据!

学术窃取是任何研究人员都需要警惕的问题。随着技术的发展&#xff0c;虽然研究工作变得更加高效&#xff0c;但同时也暴露了更多的安全漏洞&#xff0c;尤其是在数据传输和存储过程中。为了解决这一问题&#xff0c;梅子AI论文工具采用了阿里云加密技术&#xff0c;提供了一个…...

leetcode经典算法题总结

针对leetcode算法题常见的五大经典复杂算法进行如下总结&#xff1a; &#xff08;1&#xff09;分治法 把一个复杂的问题分成两个或更多的相同或相似的子问题&#xff0c;再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解&#xff0c;原问题的解即子问题的解…...

运维工具之ansible

Ansible 1.什么是ansible? ​ ansible是基于ssh架构的自动化运维工具&#xff0c;由python语言实现&#xff0c;通过ansible可以远程批量部署等。 2.部署前提 ​ 控制端需要安装ansible,被控制端要开启ssh服务&#xff0c;并允许远程登录&#xff0c;被管理主机需要安装py…...

基于 CSS Grid 的简易拖拉拽 Vue3 组件,从代码到NPM发布(1)- 拖拉拽交互

基于特定的应用场景&#xff0c;需要在页面中以网格的方式&#xff0c;实现目标组件在网格中可以进行拖拉拽、修改大小等交互。本章开始分享如何一步步从代码设计&#xff0c;最后到如何在 NPM 上发布。 请大家动动小手&#xff0c;给我一个免费的 Star 吧~ 大家如果发现了 Bug…...

【华为HCIP实战课程六】OSPF邻居关系排错网络子网掩码问题,网络工程师

一、链路上网络和掩码引发的OSPF邻居问题 R3和R4已经建立正常的ospf邻居关系 更改IP地址前R3接口IP地址 interface Serial2/0/0 link-protocol ppp ip address 10.1.34.3 255.255.255.240 [R3-Serial2/0/0]ip address 10.1.88.2 255.255.255.240 更改为10.1.88.2 R3和R4虽…...

基础教程 | 用VuePress搭建一个简单的个人博客(附源码)

先附上自己个人博客页面&#xff1a;https://illusionno.github.io/ 源码也在这里&#xff1a;https://github.com/illusionno/my-blog &#xff08;如果觉得有帮助&#xff0c;可以点颗star✨&#xff09; 使用的主题是vuepress-theme-reco2.x&#xff0c;并在上面进行了一些调…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...