【链表】LC 19.删除链表的倒数第 N 个结点
文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析2、解题代码三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接19.删除链表的倒数第 N 个结点2、题目描述二、个人思路整理1、思路分析也可以参考博主该篇博客【代码随想录】LC 19.删除链表的倒数第 N 个结点核心思路快慢双指针具体步骤引入虚拟头节点dummy-next head。设置虚拟头节点可以统一处理“删除头节点”的边界情况避免单独写if判断。构建滑动窗口间距让fast指针先走n 1 n 1n1步。此时fast与slow之间恰好相隔n nn个节点。双指针同步前进fast和slow同时向后移动直到fast nullptr即fast走到了链表末尾的空位置。此时slow恰好停在待删除节点的前一个节点。执行删除slow-next slow-next-next并释放被删除节点的内存C中建议手动delete避免内存泄漏。2、解题代码/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */classSolution{public:ListNode*removeNthFromEnd(ListNode*head,intn){ListNode*dummynewListNode(0,head);ListNode*fastdummy;ListNode*slowdummy;// fast先走 n 1 步for(inti0;in;i){fastfast-next;}// fast 和 slow 同时向后走直到 fast 越界while(fast!nullptr){fastfast-next;slowslow-next;}// 此时 slow 正好指向待删除节点的前驱ListNode*toDeleteslow-next;slow-nextslow-next-next;deletetoDelete;// 释放内存ListNode*ansdummy-next;deletedummy;returnans;}};复杂度分析时间复杂度O ( L ) O(L)O(L)仅需遍历一次链表L LL为链表长度。空间复杂度O ( 1 ) O(1)O(1)常数级变量空间。三、知识风暴快慢双指针是本题的核心思想让fast指针先走n 1 n 1n1步与slow拉开n nn个节点的间距然后两者同步前进。当fast走到链表末尾的空位置时slow恰好停在待删除节点的前驱从而一次遍历即可完成删除。算法核心思想固定间距fast先走n 1 n 1n1步使fast与slow之间恰好相隔n nn个节点。同步前进fast与slow同时向后移动直到fast nullptr此时slow指向待删除节点的前驱。一次遍历整个过程只需遍历链表一次时间复杂度为O ( L ) O(L)O(L)。虚拟头节点引入dummy统一处理「删除头节点」的边界情况避免单独写if判断。常见对比快慢双指针 vs 其他思路方法核心思路时间复杂度空间复杂度适用场景快慢双指针固定间距 同步前进一次遍历完成删除O ( L ) O(L)O(L)O ( 1 ) O(1)O(1)本题标准解法面试最常考察两次遍历先求链表长度再定位待删除节点的前驱O ( L ) O(L)O(L)O ( 1 ) O(1)O(1)思路直观但需遍历两次递归回溯递归到末尾后回溯计数找到待删除节点O ( L ) O(L)O(L)O ( L ) O(L)O(L)递归栈链表较长时可能栈溢出不推荐使用要点虚拟头节点dummy-next head统一处理删除头节点的边界情况代码更简洁。步数计算fast先走n 1 n 1n1步而不是n nn步这样slow最终停在待删除节点的前驱而非待删除节点本身。循环条件while (fast ! nullptr)让fast走到链表末尾的空位置时停止。删除操作slow-next slow-next-next并释放被删除节点的内存C 中建议手动delete避免内存泄漏。边界处理当n等于链表长度时删除的是头节点虚拟头节点可避免单独判断。算法变体与扩展删除链表中间节点fast每次走两步、slow每次走一步fast到末尾时slow恰好在中间对应 LeetCode 876。判断链表是否有环fast每次走两步、slow每次走一步若相遇则有环对应 LeetCode 141。寻找链表环的入口在判断有环的基础上让slow从头节点重新出发与fast同速前进相遇点即为环入口对应 LeetCode 142。寻找链表中点fast每次走两步、slow每次走一步fast到末尾时slow即为中点常用于归并排序的切分。与其他算法的对比快慢双指针O ( L ) O(L)O(L)时间、O ( 1 ) O(1)O(1)空间一次遍历即可完成删除是本题最优解。两次遍历先求长度再定位思路简单但需遍历两次效率略低。递归回溯代码优雅但递归深度等于链表长度长链表下可能栈溢出不具实用性。相关 LeetCode 例题19. 删除链表的倒数第 N 个结点本题快慢双指针876. 链表的中间结点快慢指针找中点141. 环形链表快慢指针判断是否有环142. 环形链表 II快慢指针找环入口

相关新闻

AI 写我的双端项目,只认鸿蒙不认小程序:祸根是注册表里的排列顺序

AI 写我的双端项目,只认鸿蒙不认小程序:祸根是注册表里的排列顺序

结论先说:tri-coding 拿哪套编码规范写你的代码,不取决于它多聪明,而取决于 tech-skills/registry.md 那张 25 行表格的排列顺序。我一个鸿蒙加微信小程序双端的项目,两端特征文件都命中了,它只加载了排在第 67 行的 a…

2026/11/10 12:33:09 阅读更多 →
水稻杂草分割数据集 水稻杂草的语义分割任务 来做数据集准备、模型配置、训练评估等

水稻杂草分割数据集 水稻杂草的语义分割任务 来做数据集准备、模型配置、训练评估等

6类水稻杂草分割数据集 数据集有图像904张 图像大小是512x512 VOC格式,可支持UNet、DeepLabv3、SegFormer等模型 可直接使用 图像未经任何亮度和噪声等预处理 使用UNet模型进行水稻杂草的语义分割任务,包括数据集准备、模型配置、训练评估以及构建一…

2026/11/8 13:49:03 阅读更多 →
电商比价系统不是爬虫练习,而是多源数据融合工程

电商比价系统不是爬虫练习,而是多源数据融合工程

简介:本资源是一套面向计算机专业本科生的毕业设计级商品比价系统实现方案,聚焦Python定向爬虫开发与多范式工程实践,适用于毕业设计、课程设计及综合大作业场景。压缩包共16个文件(含10个核心Python源码、3个编译缓存文件、1个SQ…

2026/10/25 16:12:14 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/16 8:22:12 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/16 6:41:34 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/16 8:22:12 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/16 8:22:12 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/16 7:30:18 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/16 8:22:12 阅读更多 →

日新闻

周新闻

月新闻