前言
链表练习，继续
题目：力扣【19.删除链表的倒数第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
进阶：
你能尝试使用一趟扫描实现吗？
第一次尝试
先不考虑进阶，看如何实现。
思路：重点是什么找到倒数第n个节点。
- 删除节点操作：用cur指向被删除节点的前一个节点。所以肯定得要一个虚拟头节点；
- 初始：cur = dummy_node；判断cur是不是在删除目标的前一个节点的位置？
- 用search = cur，将search后移n位，看search->next是否为空：
- n=1，将cur位置后移1位，search->next==nullptr;
- n=2，将cur位置后移2位，search->next==nullptr;
- n=3，将cur位置后移3位，search->next==nullptr;
- 依次类推
代码实现（测试通过）
/*** 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_node = new ListNode(0,head);ListNode* cur = dummy_node;while(cur->next != nullptr){ListNode* search = cur;for(int i=0;i < n ;i++){search = search->next;}if(search->next == nullptr){//交换ListNode* tmp = cur->next;cur->next = cur->next->next;delete tmp;break;}cur = cur->next;}head = dummy_node->next;delete dummy_node;return head;}
};
检查：head=nullptr，符合逻辑。n=1，for循环条件判断正确。所以通过测试。
分析时间复杂度：
while循环最差情况要遍历整个链表长度，for循环最差情况下执行n*(n+1)/2次，所以整体时间复杂度O(n^3)。
进阶
尝试使用一趟扫描。
思路：同样是线性结构，数组里面有快慢指针。这里能不能也用快慢指针？类似滑动窗口？
代码实现：
/*** 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_node = new ListNode(0,head);ListNode* slow = dummy_node;ListNode* fast = dummy_node->next;int num = 1;//计数链表总长度if(slow->next != nullptr){while(fast->next != nullptr){fast = fast->next;num++;}if(num < n ){ //完善n超出链表长度，此时不删除，返回原链表,抛出异常throw out_of_range("n > list_length");return head;}for(int i = 0;i < num-n ;i++){slow = slow->next;}ListNode* tmp = slow->next;slow->next = slow->next->next;delete tmp;}head = dummy_node->next;delete dummy_node;return head;}
};
思路正确：
- 让fast先找到链表的最后一个元素，同时计数num，得到链表的总元素。
- 收缩窗口，移动slow，移动num-n次，指向删除目标的前一个节点。slow到达位置之后，开始链表删除操作。
思路来源：个人博客【算法力扣刷题记录四【长度最小的子数组】】，学习到滑动窗口，同样是线性规则，所以借来使用。
进阶成功！！！
代码随想录学习
学习内容
同样是定义fast和slow，但过程也有区别。
我的操作：fast直接走到链表结尾，得出链表节点总数，再让slow后移num-n，到达删除目标的前一个位置。
参考操作：
- 让fast先走n步，这样窗口内包含n个节点，再让fast和slow同时移动，窗口内始终保持n个节点，当fast=nullptr时，slow恰好指向倒数第n个节点。
- 由于删除操作，需要slow指向倒数第（n+1）个节点，所以修正让fast先走n+1步.
代码实现：
/*** 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_node = new ListNode(0,head);ListNode* slow = dummy_node;ListNode* fast = dummy_node;while(fast != nullptr && n >= 0){ //n >= 0确保fast先走了n+1步fast = fast->next;n--;}if(n < 0){ //如果输入的n大于链表长度，n<0才算fast走到位，否则fast没走到位，但又已经到达链表尾部。返回原链表，不操作。不然就会把头节点删除，因为slow没有移动。while (fast != nullptr ){fast = fast->next;slow = slow->next;}ListNode* tmp = slow->next;slow->next = slow->next->next;delete tmp;}else{ //当n输入超过链表长度，抛出异常。throw out_of_range("n out of list range");}head = dummy_node->next;delete dummy_node;return head;}
};参考答案在第11行有操作空指针的风险，只是力扣用例没有检出来。
所以我在if(n < 0)可以保证输入的n小于链表长度，更完善。如果输入n超过链表长度，抛出out_of_range异常。
可以回过头看[进阶]目录下代码完善。
总结
- 删除链表节点：加虚拟头结点
- “滑动窗口”思路：个人和参考，两种操作。
- 代码随想录参考11行，个人认为有缺陷，没有保证n小于链表长度，作了补充。
（欢迎指正，转载标明出处）
