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,并在上面进行了一些调…...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...
el-switch文字内置
el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
智能AI电话机器人系统的识别能力现状与发展水平
一、引言 随着人工智能技术的飞速发展,AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术,在客户服务、营销推广、信息查询等领域发挥着越来越重要…...
STM32HAL库USART源代码解析及应用
STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...
UE5 音效系统
一.音效管理 音乐一般都是WAV,创建一个背景音乐类SoudClass,一个音效类SoundClass。所有的音乐都分为这两个类。再创建一个总音乐类,将上述两个作为它的子类。 接着我们创建一个音乐混合类SoundMix,将上述三个类翻入其中,通过它管理每个音乐…...
数据分析六部曲?
引言 上一章我们说到了数据分析六部曲,何谓六部曲呢? 其实啊,数据分析没那么难,只要掌握了下面这六个步骤,也就是数据分析六部曲,就算你是个啥都不懂的小白,也能慢慢上手做数据分析啦。 第一…...
【版本控制】GitHub Desktop 入门教程与开源协作全流程解析
目录 0 引言1 GitHub Desktop 入门教程1.1 安装与基础配置1.2 核心功能使用指南仓库管理日常开发流程分支管理 2 GitHub 开源协作流程详解2.1 Fork & Pull Request 模型2.2 完整协作流程步骤步骤 1: Fork(创建个人副本)步骤 2: Clone(克隆…...
EEG-fNIRS联合成像在跨频率耦合研究中的创新应用
摘要 神经影像技术对医学科学产生了深远的影响,推动了许多神经系统疾病研究的进展并改善了其诊断方法。在此背景下,基于神经血管耦合现象的多模态神经影像方法,通过融合各自优势来提供有关大脑皮层神经活动的互补信息。在这里,本研…...
比特币:固若金汤的数字堡垒与它的四道防线
第一道防线:机密信函——无法破解的哈希加密 将每一笔比特币交易比作一封在堡垒内部传递的机密信函。 解释“哈希”(Hashing)就是一种军事级的加密术(SHA-256),能将信函内容(交易细节…...
