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

约 3 分钟
文章信息 26 个分类 3 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 100-200 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 滴滴 京东 华为 拼多多 网易 小米 商汤 虾皮 哔哩哔哩 小红书 LeetCode 热题 100 面试经典 150 题
标签
双指针 链表 快慢指针问题
目录

题目描述

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

image-20221016001835216

image-20221016001841890

题意分析

给定单链表的头节点和整数 n，要求删除「倒数第 n 个」节点并返回新的头节点。单链表只能从头向后单向访问，无法从尾部倒着数，「倒数」与「单向」之间的矛盾就是本题的核心。

题目保证 1 <= n <= sz（sz 为链表长度），即 n 一定有效，不需要处理「倒数位置超出链表长度」的容错；但 n == sz 时删除的恰好是头节点，此时返回值不再是原来的 head，这是必须覆盖的边界。另一处隐含要求：单链表删除节点必须先拿到它的前驱，而头节点天然没有前驱。

链表长度最多 30，任何线性做法都能通过；真正的考点藏在进阶要求里——「只扫描一遍」，这决定了两种写法在面试中的分量并不相同。

解法：快慢指针

核心思路

创建指向头节点的哨兵，让快指针先走 n + 1 步，再让快慢指针同步前进。快指针到达空节点时，慢指针恰好停在待删节点的前驱，直接跳过其后继即可。

解题步骤

  • 创建哨兵 dummy，令 fast、slow 都从哨兵出发。
  • fast 先走 n + 1 步，使两指针保持固定间距。
  • 两指针同步移动，直到 fast 为空。
  • 此时 slow.next 是待删节点，修改指向并返回 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)$。

关键点总结

  • 删除节点需要定位其前驱，因此两指针间距是 n + 1。
  • 哨兵统一处理删除头节点的情况。
  • 预走步数、循环终止条件必须配套，最终返回 dummy.next。

易错点总结

  • fast 只走 n 步却仍循环到 fast == null，会让 slow 停在待删节点而非前驱。
  • 不使用哨兵时，删除头节点需要额外特判。
  • 删除操作应修改 slow.next，不能只移动 slow。
  • 返回原 head 会在删除头节点时得到错误结果。

相似题目

题目 难度 考察点
876. 链表的中间结点 简单 双指针从等距间隔换成一倍速对两倍速找中点
剑指 Offer 22. 链表中倒数第k个节点 简单 只定位不删除，间距取 k 即可且无需哨兵
面试题 02.02. 返回倒数第 k 个节点 简单 同款等距定位，但返回节点值而非改链
LCR 021. 删除链表的倒数第 N 个结点 中等 本题镜像题，可用来自测删头边界
61. 旋转链表 中等 倒数定位叠加 k 取模与成环再断环的操作