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

约 5 分钟
文章信息 31 个分类 2 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 100-200 LeetCode 热题 100 面试经典 150 题 腾讯 字节 阿里 华为 微软 美团 拼多多 京东 小米 百度 网易 小红书 快手 滴滴 携程 B站 虾皮 顺丰 招行 商汤 深信服 度小满 猿辅导
标签
双指针 链表

题目描述

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

image-20260928190824563

image-20260928190824564

题意分析

给定单链表的头节点 head 和整数 n，删除从链表末尾数起的第 n 个节点，返回删除后的头节点。倒数第一个节点就是尾节点；若链表长度为 L，待删节点就是从头数起的第 L - n + 1 个节点。

题目保证链表非空，且 1 <= n <= L，因此待删节点一定存在。只删除这一个节点，其余节点的先后顺序保持不变。删除头节点后需要返回新的头节点；链表只有一个节点时，删除后返回空。进阶要求是一趟扫描完成，不先遍历一遍计算长度。

解法：快慢指针

核心思路

[!blue]

单链表只能向后访问，不能直接从末尾倒着数。删除一个节点还需要找到它的前驱，才能把前驱的 next 改为待删节点的后继。为统一处理删除头节点，在头节点前放置哨兵 dummy，让头节点也有前驱。

让 fast、slow 都从 dummy 出发，先让 fast 走 n + 1 步，再让两个指针每次各走一步。同步移动时，它们之间始终相差 n + 1 条连接。这里的快慢指针只是出发时间不同，同步阶段的速度相同。

把哨兵的位置记为 0，真实节点记为 1 到 L，尾节点之后的空位置记为 L + 1。当 fast 到达空位置时，slow 的位置就是 (L + 1) - (n + 1) = L - n，恰好是待删节点的前一个位置。这就是间距取 n + 1 的原因。此时执行 slow.next = slow.next.next 就能完成删除。

若删除头节点，fast 预走后就已为空，slow 留在哨兵；若删除尾节点，slow 最终停在尾节点的前驱。两种边界都使用相同的接线操作，最后统一返回 dummy.next。

解题步骤

  1. 创建指向 head 的哨兵 dummy，令 fast = slow = dummy。
  2. 让 fast 前进 n + 1 步。题目保证 n <= L，因此这段移动最多恰好到达尾后的空位置。
  3. 只要 fast 不为空，就同时向后移动 fast 和 slow，保持固定间距。
  4. 循环结束后，slow.next 就是待删节点，将它跳过：slow.next = slow.next.next。
  5. 返回 dummy.next，取得删除后真实的头节点。

代码实现

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode fast = dummy;
        ListNode slow = dummy;

        // 从哨兵建立多一步的间距，让慢指针最终停在目标前驱。
        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;
    }
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Next: head}
    fast := dummy
    slow := dummy

    // 从哨兵建立多一步的间距，让慢指针最终停在目标前驱。
    for i := 0; i <= n; i++ {
        fast = fast.Next
    }

    for fast != nil {
        fast = fast.Next
        slow = slow.Next
    }

    // 修改前驱连接，跳过目标节点。
    slow.Next = slow.Next.Next
    // 删除原头后入口可能变化，应从哨兵重新取得结果头。
    return dummy.Next
}

复杂度分析

  • 时间复杂度：$O(L)$，L 为链表长度。快指针从哨兵走到链表末尾之后，慢指针也只向前移动，没有额外的计数遍历。
  • 空间复杂度：$O(1)$，只使用一个哨兵和两个指针。

关键点总结

[!green]

  • 倒数位置可以通过两个指针的固定间距转化为正向扫描。
  • 目标是找到待删节点的前驱；从哨兵出发、以 fast == null 结束时，间距应为 n + 1。
  • 哨兵统一处理删除头节点和单节点链表，结果入口始终取 dummy.next。

易错点总结

[!yellow]

  • 预走步数必须与起点、终止条件配套。这里若只走 n 步，却仍在 fast == null 时结束，slow 会停在待删节点，而非其前驱。
  • 删除需要改变链表连接。只把 slow 移向下一个节点，并不会从链表中删除任何节点。
  • 返回原 head 会在删除头节点时保留错误入口，应返回 dummy.next。
  • 不要额外移动 slow 再删除；循环结束时它已经位于正确前驱，slow.next 也因 n 有效而必然存在。

相似题目

题目 难度 关联与区别
2095. 删除链表的中间节点 中等 同样先定位待删节点前驱，原题删中点，本题利用快慢指针的固定间隔定位倒数第n项。
203. 移除链表元素 简单 同样用哑节点统一删除头节点，原题按值可能删多个，本题按位置只删一个。
82. 删除排序链表中的重复元素 II 中等 用哨兵与前驱节点统一链表删改边界；本题先用指针间隔定位倒数节点，该题删除整段重复值。
83. 删除排序链表中的重复元素 简单 用哨兵与前驱节点统一链表删改边界；本题先用指针间隔定位倒数节点，该题每段重复值只保留一个。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/95413141
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！