题解 | #删除链表的倒数第n个节点#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param n int整型
     * @return ListNode类
     */
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        if (head == null || n <= 0) {
            return head;
        }

        // 创建一个虚拟头节点，方便处理删除头节点的情况
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode slow = dummy;
        ListNode fast = dummy;

        // 让 fast 指针领先 slow 指针 n+1 步
        for (int i = 0; i <= n; i++) {
            if (fast == null) {
                return head; // 链表长度小于 n，不需要删除
            }
            fast = fast.next;
        }

        // 同时移动 slow 和 fast 指针，直到 fast 指针到达链表末尾
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }

        // 此时 slow 指向待删除节点的前一个节点
        slow.next = slow.next.next;

        return dummy.next; // 返回新的头节点
    }
}

这个实现方式也是利用了快慢指针的原理，在一次遍历中找到倒数第 n 个节点的前一个节点，然后进行删除操作。通过引入一个虚拟头节点，可以更方便地处理删除头节点的情况。

在这个实现中，我们首先让 fast 指针领先 slow 指针 n+1 步，然后同时移动两个指针，直到 fast 指针到达链表末尾。这样 slow 指针就会指向倒数第 n 个节点的前一个节点，从而可以进行删除操作。

最后，返回虚拟头节点的下一个节点作为新的链表头。

注意，题目保证 n 一定是有效的，因此无需对 n 是否超出链表长度进行额外判断。