删除链表的倒数第N个结点（最优解）

题目来源

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

题目描述

给你一个链表，删除链表的倒数第 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 个结点是一道常考且很有代表性的题目，下面来详细分析一下解决这道题的思路，帮助大家更好地理解和掌握此类链表操作问题的解法逻辑。首先，要明确解题的核心在于精准定位到倒数第 n 个结点的前一个结点，这样才能通过调整指针来顺利删除目标结点，为了方便处理各种情况尤其是当要删除的结点是链表头结点这种特殊情况，我们通常会引入虚拟头结点的技巧，同时利用快慢指针来巧妙地找到目标位置。具体步骤如下：

一是考虑边界情况，当传入的链表为空链表时，那自然不存在要删除的结点，直接返回原链表头结点即可，这是一种比较基础的边界判断，确保程序的鲁棒性。

接着创建虚拟头结点，将其 next 指针指向原链表的头结点，这个虚拟头结点的作用不容小觑，它使得后续无论是删除链表中间的结点还是头结点，都能按照统一的逻辑去处理，避免了对头结点单独编写复杂的特殊处理逻辑，让整个代码结构更加清晰简洁。

然后初始化快慢两个指针，都让它们指向刚才创建的虚拟头结点，通过让快指针先走 n + 1 步来拉开与慢指针的距离，之所以走 n + 1 步，是因为后续当快指针走到链表末尾时，慢指针刚好就能指向倒数第 n 个结点的前一个结点，这是解题的关键步骤之一，巧妙地利用了快慢指针相对移动的特性。

在快指针先走了 n + 1 步后，同时移动快慢指针，只要快指针还没走到链表末尾，就持续让它们同步向前移动，直至快指针到达链表末尾，这时慢指针就恰好停留在了倒数第 n 个结点的前一个结点位置上，为下一步的删除操作做好了精准定位。

最后就是删除操作了，只需将慢指针指向的结点的 next 指针指向其下下个结点，也就是让 slow -> next = slow -> next -> next，如此便改变了链表的指针连接关系，相当于把倒数第 n 个结点从链表中删除掉了，之后返回虚拟头结点的 next 指针所指向的结点，就是经过处理后的新链表的头结点了。通过这样一套利用虚拟头结点和快慢指针配合的思路，能清晰且高效地解决删除链表倒数第 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* Head=new ListNode(-1);Head->next=head;ListNode* fast = Head;ListNode* slow =Head;// 让 fast 指针先走 n + 1 步for (int i = 0; i <= n; ++i) fast = fast->next;// 同时移动 fast 和 slow，直到 fast 到达链表末尾while (fast) {fast = fast->next;slow = slow->next;}// 删除倒数第 n 个节点slow->next = slow->next->next;// 返回新的头节点return Head->next;}
};

这段代码旨在删除给定单链表中倒数第 n 个节点并返回新链表头节点。首先创建值为 -1 的虚拟节点 Head，其 next 指向原链表头 head，接着初始化快慢指针 fast 和 slow 都指向 Head，通过让 fast 先走 n + 1 步，然后同时移动快慢指针，直到 fast 到达链表末尾，此时 slow 指向倒数第 n 个节点的前一个节点，最后通过 slow->next = slow->next->next 删除倒数第 n 个节点，最终返回 Head->next 作为新链表的头节点，这种利用快慢指针和虚拟头节点的方法巧妙地解决了删除倒数第 n 个节点的问题，避免了复杂的边界情况处理，使代码简洁高效。