链表中等1 种解法
#19删除链表的倒数第 N 个结点
使用相距 n 个节点的快慢指针，一趟扫描定位并删除倒数第 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 <= 300 <= Node.val <= 1001 <= n <= sz
进阶：你能尝试使用一趟扫描实现吗？
解题主线
- 虚拟头节点把删除头节点统一成删除 slow.next。
- fast 先移动 n 步；随后 fast 到达尾节点时，slow 恰好位于待删节点的前驱。
解法 1：快慢指针
在虚拟头节点上建立长度为 n 的间隔，再同步移动两个指针并绕过 slow.next。
-
时间复杂度： O(L)，L 为链表长度
-
空间复杂度： O(1)
public class Solution {
static final class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public ListNode removeNthFromEnd(ListNode head, int n) {
if (n <= 0) throw new IllegalArgumentException("n must be positive");
// 虚拟头节点让删除真实头节点也统一为修改 slow.next。
ListNode dummy = new ListNode(0, head);
ListNode fast = dummy;
ListNode slow = dummy;
// fast 先走 n 步，建立与 slow 的固定间隔。
for (int i = 0; i < n; i++) {
fast = fast.next;
// 提前触底说明 n 超过链表长度。
if (fast == null) throw new IllegalArgumentException("n exceeds list length");
}
// fast 停在尾节点时，slow 恰好位于倒数第 n 个节点的前驱。
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}实现提示
- 两个旧文件实现相同，合并为一个解法并补上非法 n 的保护。
边界与易错点
- 原实现默认 n 合法，n 大于链长时会空指针；展示代码显式校验 n 与链长。
- 循环终止条件应为 fast.next != null，否则 slow 会停在待删节点而不是其前驱。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
Q019_removeEndNthListNode.javaQ019_removeNthFromEnd.java