欢迎来到李耶的频道【LeetCode面试题】。删除链表的倒数第 N 个结点 LeetCode 原题链接题目给你一个链表删除链表的倒数第n个结点并且返回链表的头结点。输入head [1,2,3,4,5], n 2 输出[1,2,3,5]输入head [1], n 1 输出[]输入head [1,2], n 1 输出[1]提示链表中结点的数目为sz1 sz 300 Node.val 1001 n sz解法一快慢指针一次遍历思路使用快慢指针快指针先走n步然后快慢指针一起移动当快指针到达链表末尾时慢指针正好指向倒数第n个结点的前驱结点。functionremoveNthFromEnd(head,n){// 使用哑结点简化边界处理constdummynewListNode(0);dummy.nexthead;letfastdummy;letslowdummy;// 快指针先走 n1 步因为 dummy 的存在for(leti0;in;i){fastfast.next;}// 快慢指针一起移动while(fast!null){fastfast.next;slowslow.next;}// 删除倒数第 n 个结点slow.nextslow.next.next;returndummy.next;}时间复杂度 / 空间复杂度O(L) / O(1)其中 L 是链表的长度优势只需一次遍历无需额外空间是面试中最推荐的写法解法二计算链表长度两次遍历思路先遍历链表计算出长度L那么倒数第n个结点就是从头部数第L - n 1个结点。再次遍历找到其前驱结点并删除。functionremoveNthFromEnd(head,n){constdummynewListNode(0);dummy.nexthead;// 第一次遍历计算链表长度letlength0;letcurrenthead;while(current!null){length;currentcurrent.next;}// 第二次遍历找到前驱结点currentdummy;for(leti0;ilength-n;i){currentcurrent.next;}current.nextcurrent.next.next;returndummy.next;}时间复杂度 / 空间复杂度O(L) / O(1)优势思路直观易于理解劣势需要两次遍历效率略低于快慢指针解法三栈辅助法思路将链表结点依次入栈然后弹出n个结点栈顶元素即为倒数第n个结点的前驱结点。functionremoveNthFromEnd(head,n){constdummynewListNode(0);dummy.nexthead;conststack[];letcurrentdummy;// 所有结点入栈while(current!null){stack.push(current);currentcurrent.next;}// 弹出 n 个结点for(leti0;in;i){stack.pop();}// 栈顶元素即为前驱结点constprevstack[stack.length-1];prev.nextprev.next.next;returndummy.next;}时间复杂度 / 空间复杂度O(L) / O(L)优势利用栈的后进先出特性思路独特劣势需要额外空间面试中不推荐解法对比解法时间 / 空间复杂度优势推荐指数快慢指针O(L) / O(1)一次遍历空间最优⭐⭐⭐⭐⭐计算链表长度O(L) / O(1)思路直观易于理解⭐⭐⭐⭐栈辅助法O(L) / O(L)思路独特利用栈特性⭐⭐⭐扩展题链表中倒数第 k 个结点输入一个链表输出该链表中倒数第 k 个结点。删除链表中的结点给定一个链表中的结点非尾结点在 O(1) 时间内将其删除。移除链表元素给你一个链表的头结点head和一个整数val删除链表中所有满足Node.val val的结点。“欲速则不达见小利则大事不成。” —— 《论语·子路》关注李耶每天一道面试题一起卷起来