Leetcode 删除链表倒数第 N 个节点
算法思想:
使用了双指针法。下面是详细的算法思想:
1. 引入虚拟头节点(dummy node)
- 为了处理链表的一些边界情况(比如删除头节点),我们在链表的头部引入了一个虚拟节点
dummy,并让它指向原来的头节点head。这样,无论我们要删除哪个节点,处理过程都变得更加统一和简单。
2. 定义两个指针:快指针(fast)和慢指针(slow)
- 我们使用两个指针,
fast和slow,最初都指向虚拟头节点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,即删除倒数第二个节点。
- 初始化:
fast和slow都指向虚拟节点dummy。 - 快指针前移:
fast先向前移动n+1 = 3步,指向节点3。 - 同步移动:同时移动
fast和slow,直到fast指向null,此时slow指向节点3的前一个节点,即节点2。 - 删除节点:通过
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 个节点
算法思想: 使用了双指针法。下面是详细的算法思想: 1. 引入虚拟头节点(dummy node) 为了处理链表的一些边界情况(比如删除头节点),我们在链表的头部引入了一个虚拟节点 dummy,并让…...
[移植] 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使用 安装 这里有三个模板,我们一般选择基础模板进行开发就好…...
40条经典ChatGPT论文指令,圈定选题和进行论文构思
目录 1、用ChatGPT圈定选题范围2、用ChatGPT生成研究方法和思路3、用ChatGPT扩展论文观点和论证4、用ChatGPT辅助论文结构设计5、如何直接使用ChatGPT4o、o1、OpenAI Canvas6、OpenAI Canvas增强了啥?7、编程功能增强 👇 ChatGPT o1网页入口在文末&#…...
在不支持WSL2的Windows环境下安装Redis并添加环境变量的方法
如果系统版本支持 WSL 2 可跳过本教程。使用官网提供的教程即可 官网教程 查看是否支持 WSL 2 如果不支持或者觉得麻烦可以按照下面的方式安装 下载 点击打开下载地址 下载 zip 文件即可 安装 将下载的 zip 文件解压到自己想要解压的地方即可。(注意&#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路由器,刷OP系统后可以中继校园网,从而让智能开关、小爱同学可以联网。 当年的价格还是55元,现在只需要30元了,价格越来越便宜,并且OP版本越来越完善了。 之前刷机过breed系统&…...
移动机器人规划控制合集
系列文章目录 提示:这里可以添加系列文章的所有文章的目录,目录需要自己手动添加 TODO:写完再整理 文章目录 系列文章目录前言 前言 认知有限,望大家多多包涵,有什么问题也希望能够与大家多交流,共同成长!…...
Type-C接口桌面显示器的优势
随着科技的飞速发展,电子设备的连接性、便捷性和高效性成为了消费者关注的重点。在这个背景下,Type-C接口桌面显示器以其卓越的性能和广泛的兼容性,正逐步成为市场上的主流选择。本文将深入探讨Type-C接口桌面显示器的优势、应用场景、市场现…...
机器学习中的熵(Entropy)是什么?
在机器学习和信息理论中,熵(Entropy)是衡量不确定性和信息量的一个重要概念。熵最初由信息论的奠基人克劳德香农(Claude Shannon)在1948年提出,用来衡量信息源的信息不确定性。在机器学习中,熵被…...
JAVA基础:Lock不同的锁形式
1.1 可重入锁 synchronized就是一个可重入锁 使用lock时,常用的ReentryLock就是可重入锁 当一个线程在获得a对象锁之后,可以继续重复获得对象锁 代码形式就是 线程调用同步代码段,在没有执行完毕前,又调用了该对象的另一个同步…...
【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 是一个强大的包管理和环境管理工具,广泛应用于数据科学…...
机器学习:回归模型和分类模型的评估方法介绍
回归模型和分类模型评估方法详解 一、回归模型评估方法 (一)均方误差(MSE) 原理 均方误差是衡量回归模型预测值与真实值之间平均平方差的指标。它通过计算预测值与真实值之差的平方的平均值来评估模型的性能。其数学公式为&…...
担心学术窃取?阿里云加密的AI论文工具帮你锁紧数据!
学术窃取是任何研究人员都需要警惕的问题。随着技术的发展,虽然研究工作变得更加高效,但同时也暴露了更多的安全漏洞,尤其是在数据传输和存储过程中。为了解决这一问题,梅子AI论文工具采用了阿里云加密技术,提供了一个…...
leetcode经典算法题总结
针对leetcode算法题常见的五大经典复杂算法进行如下总结: (1)分治法 把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解…...
运维工具之ansible
Ansible 1.什么是ansible? ansible是基于ssh架构的自动化运维工具,由python语言实现,通过ansible可以远程批量部署等。 2.部署前提 控制端需要安装ansible,被控制端要开启ssh服务,并允许远程登录,被管理主机需要安装py…...
基于 CSS Grid 的简易拖拉拽 Vue3 组件,从代码到NPM发布(1)- 拖拉拽交互
基于特定的应用场景,需要在页面中以网格的方式,实现目标组件在网格中可以进行拖拉拽、修改大小等交互。本章开始分享如何一步步从代码设计,最后到如何在 NPM 上发布。 请大家动动小手,给我一个免费的 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搭建一个简单的个人博客(附源码)
先附上自己个人博客页面:https://illusionno.github.io/ 源码也在这里:https://github.com/illusionno/my-blog (如果觉得有帮助,可以点颗star✨) 使用的主题是vuepress-theme-reco2.x,并在上面进行了一些调…...
Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
AI Agent与Agentic AI:原理、应用、挑战与未来展望
文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例:使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例:使用OpenAI GPT-3进…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
2.Vue编写一个app
1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
【论文阅读28】-CNN-BiLSTM-Attention-(2024)
本文把滑坡位移序列拆开、筛优质因子,再用 CNN-BiLSTM-Attention 来动态预测每个子序列,最后重构出总位移,预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵(S…...
dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...
算术操作符与类型转换:从基础到精通
目录 前言:从基础到实践——探索运算符与类型转换的奥秘 算术操作符超级详解 算术操作符:、-、*、/、% 赋值操作符:和复合赋值 单⽬操作符:、--、、- 前言:从基础到实践——探索运算符与类型转换的奥秘 在先前的文…...
