算法力扣刷题记录十【19.删除链表的倒数第N个节点】

前言

链表练习，继续
题目：力扣【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小于链表长度，作了补充。

（欢迎指正，转载标明出处）