C++删除链表的倒数第 N 个结点

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

代码逻辑逐行解释

采用快慢指针+虚拟头结点的标准解法，能正确实现“删除链表倒数第N个结点”的功能，下面逐行拆解核心逻辑：

一、链表节点定义
struct ListNode {
int val; // 节点存储的数值
ListNode *next; // 指向下一个节点的指针
// 无参构造函数：值为0，next为空
ListNode() : val(0), next(nullptr) {}
// 单参构造函数：指定值，next为空
ListNode(int x) : val(x), next(nullptr) {}
// 双参构造函数：指定值和下一个节点
ListNode(int x, ListNode *next) : val(x), next(next) {}
};

这是LeetCode中单向链表节点的标准定义，通过构造函数快速初始化节点。

二、核心解题函数

1. 创建虚拟头结点

ListNode* dummy = new ListNode(0, head);

作用：统一处理删除原头结点的边界情况。比如链表只有1个节点且要删除它时，若没有虚拟头结点，直接操作 head 会出现空指针问题；有了 dummy ，只需修改 dummy->next 即可。
细节： dummy 的值设为0（无实际意义）， next 指向原链表的头结点 head 。

2. 初始化快慢指针

ListNode* fast = dummy; // 快指针 ListNode* slow = dummy; // 慢指针

快慢指针都从虚拟头结点 dummy 开始，目的是通过制造指针间隔，一次遍历找到目标节点的前驱。

3. 快指针先走n步

for(int i=0; i<n; i++){ fast = fast->next; }

作用：让快指针 fast 和慢指针 slow 之间形成n个节点的间隔。比如n=2时， fast 会比 slow 超前2个节点。
举例：若链表是 [1,2,3,4,5] 、n=2，这一步后 fast 会指向节点 2 ， slow 仍指向 dummy 。

4. 快慢指针同步移动

while(fast->next != nullptr){ fast = fast->next; slow = slow->next; }

终止条件： fast->next == nullptr （快指针走到最后一个有效节点）。
作用：当快指针走到链表末尾时，慢指针会恰好停在倒数第n个节点的前驱节点。
举例：还是 [1,2,3,4,5] 、n=2的情况，这一步结束后：
fast 指向最后一个节点 5 （ fast->next 为 nullptr ）；
slow 指向节点 3 （倒数第2个节点 4 的前驱）。

5. 删除目标节点

slow->next = slow->next->next;

逻辑： slow->next 原本指向倒数第n个节点，将其改为指向该节点的下一个节点，就跳过了目标节点，实现“删除”（链表中删除节点的本质是断开引用）。
举例： slow 指向 3 时， slow->next 是 4 ，执行后 slow->next 变为 5 ，节点 4 被删除。

6. 释放内存并返回结果

ListNode* newHead = dummy->next; // 新链表的头结点是dummy的下一个节点 delete dummy; // 释放虚拟头结点的内存（避免内存泄漏） return newHead; // 返回删除节点后的链表头

细节： dummy->next 是新链表的真正头结点（若原头结点被删除， dummy->next 会指向原第二个节点；若未删除，仍指向原头结点）；最后要释放 dummy ，否则会造成内存泄漏。

三、核心逻辑总结

1. 虚拟头结点：解决删除头结点的边界问题；
2. 快指针先走n步：制造n个节点的间隔；
3. 快慢指针同步移动：找到倒数第n个节点的前驱；
4. 修改指针引用：删除目标节点；
5. 释放内存并返回：完成最终操作。

该解法的时间复杂度为O(L)（L是链表长度，仅一次遍历），空间复杂度为O(1)（仅使用常数个指针），是这道题的最优解法。

“删除链表的倒数第N个结点”的最优解是快慢指针+虚拟头结点：通过创建虚拟头结点 dummy 统一处理删除原头结点的边界问题，先让快指针从 dummy 出发走 n 步，再让快慢指针同步移动至快指针抵达链表最后一个有效节点，此时慢指针恰好指向倒数第N个节点的前驱，通过修改慢指针的 next 引用即可删除目标节点，最后释放 dummy 并返回其 next 作为新链表头；该解法仅需一次线性遍历，时间复杂度为O(L)（L为链表长度），空间复杂度为O(1)，同时需注意循环条件的准确性（快指针走 n 步、同步移动终止于 fast->next=nullptr ）和C++中的内存释放，避免越界与内存泄漏问题。