#19

中等

中频

双指针

删除链表的倒数第N个节点

这是一道围绕链表展开的高频练习。建议先掌握「双指针」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。

链表

原题练习

题目分析

给你一条链表和一个整数 n，要求删除链表的倒数第 n 个节点，并返回删除后的头节点。

比如链表是 1 -> 2 -> 3 -> 4 -> 5，n = 2，删除后结果就是 1 -> 2 -> 3 -> 5。

一句话概括：

用两个指针保持固定间距，让后面的指针最终停在待删除节点的前一个位置。

接下来怎么看推荐代码：带着这个理解再看推荐代码时，重点观察这条主线：让快指针先走 n+1 步，再和慢指针一起前进，使慢指针停在待删除节点前一个位置。

推荐代码

推荐解法：双指针

时间复杂度： O(n)

空间复杂度： O(1)

核心思路：让快指针先走 n+1 步，再和慢指针一起前进，使慢指针停在待删除节点前一个位置。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 创建哑节点，方便处理头节点可能被删除的情况
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        // 初始化快慢指针
        ListNode fast = dummy;
        ListNode slow = dummy;
        
        // 快指针先前进n+1步
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }
        
        // 快慢指针同时前进，直到快指针到达链表末尾
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        
        // 此时慢指针指向要删除节点的前一个节点，执行删除操作
        slow.next = slow.next.next;
        
        return dummy.next;
    }
}

结构化讲解

面试时怎么讲

开场思路

这题我会用快慢指针做固定间距定位，并在头部补一个哑节点处理边界。

核心过程

先让快指针从 dummy 开始走 n+1 步，和慢指针拉开固定距离。
然后快慢指针同步前进，直到快指针走到链表末尾。
此时慢指针正好停在倒数第 N 个节点的前一个位置。
最后执行一次指针跳过完成删除。

复杂度总结

时间复杂度 O(n)，空间复杂度 O(1)。

面试补一句：这题真正要定位的是“目标前驱”，不是目标节点本身。

核心思路

删除倒数第 N 个节点的核心不是倒着走，而是制造一个固定间距。快慢指针之间保持 n+1 个节点距离时，快指针到尾，慢指针正好来到目标前驱。

步骤讲解

先加哑节点统一边界

在头节点前补一个 dummy，让删除头节点的情况也能统一成“删某个节点的后继”。

为什么这样做：这样慢指针最终总能停在待删节点前一个位置，即使目标就是原头节点。

对应代码提示：ListNode dummy = new ListNode(0, head);

快指针先走 `n+1` 步

让快指针从 dummy 出发，先向前移动 n+1 次。

为什么这样做：这样快慢指针之间固定隔着 n 个节点，便于后面精确定位前驱。

对应代码提示：for (int i = 0; i <= n; i++) fast = fast.next;

快慢指针同步前进

之后让两个指针一起往前走，直到快指针走到 null。

为什么这样做：快指针到尾时，慢指针刚好停在待删除节点的前一个节点。

对应代码提示：while (fast != null) { fast = fast.next; slow = slow.next; }

跳过目标节点

执行 slow.next = slow.next.next，把倒数第 N 个节点从链表中断开。

为什么这样做：链表删除的本质是让前驱直接指向目标的后继。

对应代码提示：slow.next = slow.next.next;

易错点

快指针只走了 n 步

这样慢指针最终会停在待删节点本身，而不是前驱节点。

正确理解：如果从 dummy 出发，就要让快指针先走 n+1 步。

没加哑节点导致删头节点麻烦

当要删除的是原头节点时，没有前驱节点可以直接修改。

正确理解：统一在头部补一个 dummy。

删除前没确认慢指针位置

如果慢指针定位错了，可能删掉相邻节点。

正确理解：记住慢指针停的是目标前驱，所以删除动作一定是改 slow.next。

复杂度与适用判断

时间复杂度：O(n)

空间复杂度：O(1)

比其他方案更好在哪里：比先算链表长度再二次遍历更直接，只需一趟扫描。

适用判断：链表题里只要目标和末尾距离有关，优先考虑固定间距的双指针。

额外提醒

补 dummy 后，删头节点和删中间节点完全统一。

动画演示

如果你还没完全看懂，可以展开动画演示。

双指针动画演示

想看这段解法是怎么一步步运行的，可以展开动画继续观察。

删除链表的倒数第N个节点 - 双指针算法

Dummy

N值：

操作日志

动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。