【链表】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快慢指针找环入口