【力扣100题】15.删除链表的倒数第 N 个结点

1. 题目描述给你一个链表删除链表的倒数第n个结点并且返回链表的头结点。示例输入head [1,2,3,4,5], n 2 输出[1,2,3,5] 解释删除倒数第2个结点值为4 输入head [1], n 1 输出[] 解释删除倒数第1个结点唯一的结点链表为空 输入head [1,2], n 1 输出[1] 解释删除倒数第1个结点值为2提示链表中结点的数目为 sz 1 sz 30 0 Node.val 100 1 n sz进阶你能尝试使用一趟扫描实现吗2. 核心思想关键思想快慢指针 虚拟头节点要删除倒数第n个结点需要找到它的前一个结点。核心思路让快指针先走 n 步然后快慢指针一起走当快指针走到末尾时慢指针正好在目标结点的前一个位置。以 [1,2,3,4,5], n2 为例 初始dummy → 1 → 2 → 3 → 4 → 5 → nullptr ↑ ↑ slow fast 第1步fast 走 n2 步 fast 3走了1步 fast 4走了2步 第2步fast 和 slow 同时走 fast4, slow1 → fast-next5, slow2 fast5, slow2 → fast-nextnullptr, slow3 fast-nextnull退出 此时slow 在结点 3 的位置 slow-next 是结点 4要删除的 slow-next slow-next-next删除成功3. 多种方法解决方法一快慢指针 虚拟头节点推荐✅/** * 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;// 第一步快指针先走 n 步while(n--){fastfast-next;}// 第二步快慢指针同时走ListNode*slowdummy;while(fast-next){slowslow-next;fastfast-next;}// 第三步删除目标结点ListNode*toDeleteslow-next;slow-nextslow-next-next;deletetoDelete;returndummy-next;}};复杂度时间 O(L)空间 O(1)只遍历一次 ✅方法二计算链表长度两次遍历classSolution{public:ListNode*removeNthFromEnd(ListNode*head,intn){ListNode*dummynewListNode(0,head);// 第一次遍历计算链表长度intlength0;ListNode*currhead;while(curr){length;currcurr-next;}// 第二次遍历找到倒数第 n 个结点的前一个length-n;// 正数第 length-n1 个就是要删的currdummy;while(length--1){currcurr-next;}// 删除ListNode*toDeletecurr-next;curr-nextcurr-next-next;deletetoDelete;returndummy-next;}};复杂度时间 O(L)空间 O(1)但需要遍历两次 ❌方法三栈不推荐classSolution{public:ListNode*removeNthFromEnd(ListNode*head,intn){ListNode*dummynewListNode(0,head);stackListNode*stk;ListNode*currdummy;while(curr){stk.push(curr);currcurr-next;}// 弹出 n 个剩下的栈顶就是要删结点的前一个for(inti0;in;i){stk.pop();}ListNode*prevstk.top();prev-nextprev-next-next;returndummy-next;}};复杂度时间 O(L)空间 O(L) ❌4. 图解过程示例head [1,2,3,4,5], n 2初始状态 dummy(0) → 1 → 2 → 3 → 4 → 5 → nullptr ↑ fastdummy, slowdummy 第一步fast 先走 n2 步 fast 0→next 1走1步 fast 1→next 2走2步 第二步fast 和 slow 同时走直到 fast→next nullptr fast2, slowdummy fast-next 3 ≠ nullptr继续 fast3, slow1 fast-next 4 ≠ nullptr继续 fast4, slow2 fast-next 5 ≠ nullptr继续 fast5, slow3 fast-next nullptr退出 此时 slow 3slow-next 4要删除的结点 删除操作 slow-next slow-next-next 即3→next 5 最终 dummy → 1 → 2 → 3 → 5 → nullptr边界情况head [1], n 1初始dummy(0) → 1 → nullptr fast 先走1步 fast 1走完 fast-next nullptrwhile 不执行 slow dummy slow-next 1要删除 删除后 dummy → nullptr return dummy-next nullptr ✓5. 方法优缺点比较方法时间空间优点缺点快慢指针O(L) ✅O(1) ✅一趟扫描指针移动最少思维稍难计算长度O(L)O(1)简单直观需要两次遍历栈O(L)O(L)代码简单空间开销大推荐方法方法一快慢指针是面试和竞赛中的标准解法一趟扫描时间最优O(1) 空间掌握后代码很简洁6. 完整测试代码#includeiostream#includevectorusingnamespacestd;structListNode{intval;ListNode*next;ListNode():val(0),next(nullptr){}ListNode(intx):val(x),next(nullptr){}ListNode(intx,ListNode*next):val(x),next(next){}};classSolution{public:ListNode*removeNthFromEnd(ListNode*head,intn){ListNode*dummynewListNode(0,head);ListNode*fastdummy;while(n--){fastfast-next;}ListNode*slowdummy;while(fast-next){slowslow-next;fastfast-next;}ListNode*toDeleteslow-next;slow-nextslow-next-next;deletetoDelete;returndummy-next;}};// 辅助函数链表转 vector方便打印vectorinttoVector(ListNode*head){vectorintresult;while(head){result.push_back(head-val);headhead-next;}returnresult;}// 辅助函数vector 转链表ListNode*toList(vectorintvals){ListNode*dummynewListNode(0);ListNode*currdummy;for(intv:vals){curr-nextnewListNode(v);currcurr-next;}returndummy-next;}intmain(){Solution sol;// 测试1[1,2,3,4,5], n2 → [1,2,3,5]ListNode*h1toList({1,2,3,4,5});vectorintr1toVector(sol.removeNthFromEnd(h1,2));cout[1,2,3,4,5], n2 → [;for(inti0;ir1.size();i)coutr1[i](ir1.size()-1?,:);cout]endl;// 测试2[1], n1 → []ListNode*h2toList({1});vectorintr2toVector(sol.removeNthFromEnd(h2,1));cout[1], n1 → [;for(inti0;ir2.size();i)coutr2[i](ir2.size()-1?,:);cout]endl;// 测试3[1,2], n1 → [1]ListNode*h3toList({1,2});vectorintr3toVector(sol.removeNthFromEnd(h3,1));cout[1,2], n1 → [;for(inti0;ir3.size();i)coutr3[i](ir3.size()-1?,:);cout]endl;return0;}输出[1,2,3,4,5], n2 → [1,2,3,5] [1], n1 → [] [1,2], n1 → [1]8. 总结要点说明核心思想快慢指针快指针先走 n 步然后一起走到末尾虚拟头节点统一处理头结点删除无需单独判断关键slow 停在目标结点的前一个位置复杂度时间 O(L)空间 O(1)一趟扫描 ✅