当前位置：首页 > news >正文

19.删除链表的倒数第N个结点

news 2026/5/26 15:19:27

题目描述

前言

在对链表进行操作时，一种常用的技巧是添加一个哑节点（dummy node），它的 next 指针指向链表的头节点。这样一来，我们就不需要对头节点进行特殊的判断了

题解一(计算链表长度)(最容易想到)

思路

从头节点开始对链表进行一次遍历，得到链表的长度 L。随后我们再从头节点开始对链表进行一次遍历，当遍历到第 L−n+1 个节点时，它就是我们需要删除的节点
为了方便删除操作，我们可以从哑节点开始遍历 L−n+1 个节点。当遍历到第 L−n+1 个节点时，它的下一个节点就是我们需要删除的节点

代码

classSolution{publicListNoderemoveNthFromEnd(ListNodehead,intn){ListNodedummy=newListNode(0,head);intlength=getLength(head);ListNodecur=dummy;for(inti=1;i<length-n+1;++i){cur=cur.next;}cur.next=cur.next.next;ListNodeans=dummy.next;returnans;}publicintgetLength(ListNodehead){intlength=0;while(head!=null){++length;head=head.next;}returnlength;}}

复杂度分析

时间复杂度：O(L)，其中 L 是链表的长度
空间复杂度：O(1)

题解二(双指针)(最优雅最高效)

思路

如果我们要找到倒数第nnn个节点，可以让一个“快指针”先走nnn步，然后“快指针”和“慢指针”再一起同步移动。当“快指针”走到链表末尾(nullnullnull)时，“慢指针”刚好就停在倒数第nnn个节点上

具体步骤

代码

classSolution{publicListNoderemoveNthFromEnd(ListNodehead,intn){// 1. 创建虚拟头节点，统一操作逻辑（处理删除真正头节点的情况）ListNodedummy=newListNode(0,head);// 2. 初始化快慢指针，都指向虚拟头节点ListNodefast=dummy;ListNodeslow=dummy;// 3. 让 fast 指针先走 n + 1 步for(inti=0;i<=n;i++){fast=fast.next;}// 4. fast 和 slow 同时走，直到 fast 到达链表末尾的 nullwhile(fast!=null){fast=fast.next;slow=slow.next;}// 5. 此时 slow 停在倒数第 n 个节点的前一个节点，执行删除操作slow.next=slow.next.next;// 6. 返回新的头节点（注意不要返回 head，因为 head 有可能被删除了）returndummy.next;}}

复杂度分析

时间复杂度：O(L)\mathcal{O}(L)O(L)，其中LLL是链表的长度。fast 指针和 slow 指针最多只遍历链表一次，因此实现了一趟遍历的解法
空间复杂度：O(1)\mathcal{O}(1)O(1)。只使用了常数个额外的指针变量 fast、slow 和 dummy，没有开辟额外的线性空间

题解三(栈)

思路

在遍历链表的同时将所有节点依次入栈。
根据栈「先进后出」的原则，我们弹出栈的第 n 个节点就是需要删除的节点
并且目前栈顶的节点就是待删除节点的前驱节点

代码

classSolution{publicListNoderemoveNthFromEnd(ListNodehead,intn){ListNodedummy=newListNode(0,head);Deque<ListNode>stack=newLinkedList<ListNode>();ListNodecur=dummy;//这里要把dummy节点也入栈,具体原因请看下文分析while(cur!=null){stack.push(cur);cur=cur.next;}for(inti=0;i<n;++i){stack.pop();}ListNodeprev=stack.peek();prev.next=prev.next.next;ListNodeans=dummy.next;returnans;}}