力扣题目解析--删除链表的倒数第n个节点

题目

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

代码展示

/*** 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 *dummy=new ListNode(0);dummy->next=head;ListNode *current=dummy;ListNode *fast=dummy;ListNode *slow=dummy;for(int i=0;i<n;i++){if(fast->next==nullptr){delete dummy;return head;}fast=fast->next;}while (fast->next!=nullptr){fast=fast->next;slow=slow->next;}ListNode* toDelete =slow->next;slow->next=slow->next->next;delete toDelete;ListNode* newHead=dummy->next;delete dummy;return newHead;}
};

写者心得

要想搞明白这个题就必须得先看得懂题目在开头给的注释，那里面有关于对于列表是怎么设置的，写者就是在先去搞明白他是怎样设置列表之后再写代码的。这结构体设置的并不难，但其中有一个点是我搞错了的，val它其实是链表中的值，而我一直把它当做链表的一个元素来看待，所以造成了一些错误。代码有一些写的比较好的地方：

1.虚拟头节点

对比分析

1. 删除头节点：

   • 没有虚拟头节点：需要单独处理头节点的删除情况，代码复杂度增加。
   • 有虚拟头节点：删除头节点和其他节点的操作一致，代码简洁。

2. 代码简洁性：

   • 没有虚拟头节点：需要更多的条件判断，代码冗长。
   • 有虚拟头节点：代码结构更清晰，易于理解和维护。

虚拟头节点在链表中是非常常用的，其实它的作用很简单，就是当你在处理列表中节点的时候，有可能会处理到头节点的情况，正是因为我们把这个头节点虚拟化了，所以就不需要考虑这个问题了，这样子可以省去我们许多关于头节点的条件设置

2.双指针

但其实这个双指针和我们在前面所用到的双指针是完全不同的两个东西，过去的双指针是为了遍历数组 ，而这个双指针则是为了寻找节点，其实这个思路很像是双循环，一个负责遍历，另一个则负责删除，所以一个指针设为快指针，另一个指针设为慢指针，这样就可以在链表之中寻找节点，我想这个方法应该和双循环暴力破解有异曲同工之处，而在接下来我们处理链表问题的时候，会经常用到这样子的思路和这样的做法。

代码解析

/*** 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) {}* };*/

这部分定义了一个单链表节点的结构体 ListNode，包含三个构造函数：

• 默认构造函数：ListNode() : val(0), next(nullptr) {}
• 带一个参数的构造函数：ListNode(int x) : val(x), next(nullptr) {}
• 带两个参数的构造函数：ListNode(int x, ListNode *next) : val(x), next(next) {}

创建虚拟头节点

        ListNode *dummy = new ListNode(0);dummy->next = head;

• 创建一个虚拟头节点 dummy，其值为 0，next 指向原链表的头节点 head。
• 虚拟头节点的作用是简化边界条件的处理，特别是删除头节点的情况。

初始化指针

        ListNode *current = dummy;ListNode *fast = dummy;ListNode *slow = dummy;

• 初始化三个指针 current、fast 和 slow，都指向虚拟头节点 dummy。

快指针先走 n 步

        for (int i = 0; i < n; i++) {if (fast->next == nullptr) {delete dummy;return head;}fast = fast->next;}

• 使用一个 for 循环让快指针 fast 先向前移动 nn 步。
• 在每次移动前，检查 fast->next 是否为 nullptr，如果是，说明链表长度小于 nn，直接返回原链表。
• 如果链表长度大于等于 nn，继续移动快指针。

同步移动快指针和慢指针

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

• 使用一个 while 循环同步移动快指针 fast 和慢指针 slow，直到快指针到达链表的末尾。
• 当快指针到达链表末尾时，慢指针正好指向倒数第 nn 个节点的前一个节点。

删除慢指针的下一个节点

        ListNode* toDelete = slow->next;slow->next = slow->next->next;delete toDelete;

• 记录要删除的节点 toDelete，即 slow->next。
• 将慢指针的 next 指针指向要删除节点的下一个节点，从而跳过要删除的节点。
• 释放要删除节点的内存。

返回新的头节点

        ListNode* newHead = dummy->next;delete dummy;return newHead;}
};

• 返回新的头节点 newHead，即 dummy->next。
• 释放虚拟头节点的内存。
• 返回新的头节点。

总结

通过使用虚拟头节点和双指针法，我们可以有效地删除链表中的倒数第 nn 个节点。虚拟头节点简化了边界条件的处理，双指针法确保了我们能够准确地找到要删除的节点的位置。