day138—快慢指针—删除链表的倒数第N个结点（LeetCode-19）

题目描述

给你一个链表，删除链表的倒数第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 个节点，采用「虚拟头节点 + 快慢指针」的经典方法实现，时间复杂度O(n)、空间复杂度O(1)，能高效且优雅地处理删除头节点等边界情况。

核心逻辑

代码通过快慢指针制造n步的间距，让快指针先走到指定位置，再同步移动快慢指针，最终定位到倒数第 n 个节点的前驱节点，完成删除：

1. 虚拟头节点初始化：创建虚拟头节点node并指向原链表头head，避免删除原头节点时的边界问题；
2. 快慢指针拉开间距：快指针fast先从虚拟头节点出发，向前移动n步，此时快慢指针间距为n；
3. 同步移动找前驱：快慢指针同步向后移动，直到快指针走到链表末尾（fast->next为空），此时慢指针slow恰好指向「倒数第 n 个节点的前驱节点」；
4. 删除目标节点：将慢指针的next指向其下下个节点，跳过倒数第 n 个节点，完成删除；
5. 返回结果：返回虚拟头节点的next（即删除后的链表头）。

总结

1. 核心思路：利用快慢指针的n步间距，将 “找倒数第 n 个节点” 转化为 “找正数的前驱节点”，避免先遍历统计长度的二次遍历；
2. 关键设计：虚拟头节点解决了 “删除原链表头节点” 的边界问题，无需额外判断；
3. 效率特点：仅一次遍历完成查找和删除，时间O(n)，空间仅用几个指针，是该问题的最优解法。

函数源码：

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* node=new ListNode(); node->next=head; ListNode* slow=node; ListNode* fast=node; for(int i=0;i<n;i++){ fast=fast->next; } while(fast->next){ fast=fast->next; slow=slow->next; } //ListNode* nxt=slow->next; slow->next=slow->next->next; //delete nxt; return node->next; } };