XingHuiSamaの宝藏之地

给你一个链表，删除链表的倒数第 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

1. 算法核心思想：长度转换与前驱定位

单向链表的特性决定了我们无法直接从后往前遍历。因此，“删除倒数第 N 个节点”的直接解法是将其转化为正向问题：先求出链表的总长度 L，倒数第 N 个节点即为正数第 L−N+1 个节点。

要删除一个节点，必须先找到它的前驱节点（即排在它前面的那一个节点）。因此，引入了“虚拟头节点（Dummy Node）”，统一了所有节点的删除逻辑。从虚拟头节点出发，恰好前进 L−N 步，就能准确停在待删除节点的前驱位置，从而通过简单的指针修改完成删除。

2. 逻辑拆解

引入虚拟头节点：创建 head1 并令其指向 head。这一步非常关键，它保证了即使要删除的是原链表的第一个节点（即 L=N 时），算法逻辑依然适用，避免了单独编写 if 分支来处理换头操作。
总长度统计：游标指针 p 从 head 开始遍历。因为 while 循环的终止条件是 p->next != 0，这意味着循环结束时 p 停留在最后一个节点，并没有走到 NULL。为了弥补这个差值，count 初始化为 1，从而正确统计出链表的真实节点总数。
步数转换与步进：计算 s = count - n，这代表为了到达目标节点的前驱位置，指针需要移动的次数。声明 start 指针从 head1（虚拟头节点）出发，严格执行 s 次后移操作。
断链与返回：循环结束后，start 停在待删除节点的前方。执行 start->next = start->next->next，直接在链表结构中跨过目标节点。最后返回 head1->next，即真正的链表头。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // 1. 初始化计数器与虚拟头节点
        int count = 1; 
        ListNode* head1 = new ListNode(0);
        head1->next = head;

        ListNode* p = head;

        // 2. 第一次遍历：统计链表总长度
        while (p->next != 0) {
            p = p->next;
            count++;
        }

        // 计算需要从虚拟头节点前进的步数
        int s = count - n;
        ListNode* start = head1;

        // 3. 第二次遍历：寻找待删除节点的前驱节点
        while (s != 0) {
            s--;
            start = start->next;
        }

        // 4. 执行删除操作：跳过目标节点
        start->next = start->next->next;

        return head1->next;
    }
};

3. 复杂度分析

时间复杂度：O(L)。（L 为链表的长度）。算法完整遍历了一次链表来获取长度，接着又遍历了 L−N 个节点来寻找删除位置。总的访问节点数量为 2L−N，耗时严格处于线性级别。
空间复杂度：O(1)。只在堆内存中额外申请了一个虚拟头节点 head1，以及若干个整型变量和指针变量，内存占用不随链表规模扩大而增加。