【LeetHOT100】删除链表的倒数第 N 个结点——Java多解法详解

一、题目描述

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

给你一个链表，删除链表的倒数第n个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5]，n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1]，n = 1
输出：[]

示例 3：

输入：head = [1,2]，n = 1
输出：[1]

提示：

• 链表中结点的数目为sz

• 1 <= sz <= 30

• 0 <= Node.val <= 100

• 1 <= n <= sz

进阶：你能尝试使用一趟扫描实现吗？

二、解题思路概览

删除倒数第 N 个结点，核心是找到它的前驱节点。常见解法有三种：

三、解法一：两次遍历（计算链表长度）

3.1 思路

1. 第一次遍历：计算链表的总长度length；

2. 倒数第n个结点，就是正数第length - n个结点（从 1 开始计数）；

3. 第二次遍历：找到第length - n - 1个结点（前驱），将其next指向下下个结点；

4. 注意：如果删除的是头结点，需要特殊处理。

3.2 代码实现

java

class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { // 1. 计算链表长度 int length = 0; ListNode p = head; while (p != null) { length++; p = p.next; } // 2. 计算需要删除的节点是正数第几个（从1开始） int targetIndex = length - n + 1; // 3. 处理删除头结点的情况 if (targetIndex == 1) { return head.next; } // 4. 找到要删除节点的前驱 ListNode prev = head; for (int i = 1; i < targetIndex - 1; i++) { prev = prev.next; } // 5. 删除节点 prev.next = prev.next.next; return head; } }

3.3 复杂度分析

• 时间复杂度：O(L)，遍历两次链表。

• 空间复杂度：O(1)，只用了几个指针变量。

四、解法二：快慢指针（一次遍历）⭐

4.1 思路

使用两个指针slow和fast，初始化都指向哑结点（dummy node）：

• fast先移动n步；

• 然后slow和fast同时移动，直到fast到达链表末尾；

• 此时slow.next就是要删除的节点（因为slow和fast之间始终相隔n个节点）；

• 删除slow.next即可。

使用哑结点可以避免对头结点的特殊处理，使代码更统一。

4.2 代码实现

java

class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0, head); ListNode slow = dummy; ListNode fast = dummy; // 快指针先走 n 步 for (int i = 0; i < n; i++) { fast = fast.next; } // 同时移动，直到 fast 到达末尾 while (fast.next != null) { slow = slow.next; fast = fast.next; } // 删除 slow.next slow.next = slow.next.next; return dummy.next; } }

4.3 图解示例

以head = [1,2,3,4,5]，n = 2为例：

text

初始: dummy → 1 → 2 → 3 → 4 → 5 → null slow, fast 都指向 dummy 第1步: fast 先走 n=2 步 dummy → 1 → 2 → 3 → 4 → 5 → null ↑ ↑ slow fast 第2步: 同时移动，直到 fast.next == null dummy → 1 → 2 → 3 → 4 → 5 → null ↑ ↑ slow fast 此时 slow.next 指向节点 4，正是要删除的节点 执行 slow.next = slow.next.next 即可删除节点 4

4.4 复杂度分析

• 时间复杂度：O(L)，只遍历一次链表。

• 空间复杂度：O(1)。

五、解法三：使用栈

5.1 思路

1. 遍历链表，将所有节点依次压入栈中；

2. 从栈顶弹出n个节点（即倒数第n个节点会留在栈顶）；

3. 再弹出一次，得到倒数第n个节点的前一个节点；

4. 修改指针完成删除。

5.2 代码实现

java

class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0, head); Deque<ListNode> stack = new ArrayDeque<>(); ListNode p = dummy; // 将链表节点（包括哑结点）全部入栈 while (p != null) { stack.push(p); p = p.next; } // 弹出 n 个节点，此时栈顶就是倒数第 n 个节点的前驱 for (int i = 0; i < n; i++) { stack.pop(); } ListNode prev = stack.peek(); // 前驱节点 prev.next = prev.next.next; // 删除目标节点 return dummy.next; } }

5.3 复杂度分析

• 时间复杂度：O(L)，遍历一次 + 栈操作 O(1) 每次。

• 空间复杂度：O(L)，栈需要存储所有节点。

六、解法对比与总结

6.1 面试建议

• 首选快慢指针法：一次遍历 + O(1) 空间，完美满足进阶要求，也是面试官最期待的答案。

• 注意使用哑结点（dummy node）来简化头结点的删除逻辑。

• 边界条件：n有效（1 ≤ n ≤ sz），题目已保证，无需额外校验。

6.2 常见错误

1. 忘记处理头结点删除：如果不使用哑结点，需要单独判断targetIndex == 1的情况。

2. 快慢指针初始位置错误：fast先走n步，如果初始都指向head，则删除头结点时会出现空指针异常。使用哑结点可避免。

3. 快慢指针移动条件：应该是fast.next != null，而不是fast != null，否则slow会多走一步。

七、相关链接

• 题目链接：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

• 官方题解：删除链表的倒数第 N 个结点官方题解