一、编程题：19. 删除链表的倒数第 N 个结点（双指针-快慢指针）
1.题目描述
??给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 LeetCode题目链接。
2.示例1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
3.示例2：
输入：head = [1], n = 1
输出：[]
4.示例3：
输入：head = [1,2], n = 1
输出：[1]
5.提示：
- 链表中结点的数目为 sz
- 1 <= sz <= 30
- 0 <= Node.val <= 100
- 1 <= n <= sz
6.进阶：
- 你能尝试使用一趟扫描实现吗？
二、解题思路
??可以根据滑动窗口的思想来解决本题；
??这题采用双指针，本题主要关键点为：
- 1.该怎么去移动这两个指针？这一点要理清楚。这里双指针移动就比较简单了，分别向下移动一步即可；
1.思路
解决方法1（个人想法）：
快慢指针第一次相遇：
- Step 1.创建指针fast和slow均指向head，首先要先找到快指针fast的位置，fast与slow之间间隔n-1个节点;
- Step 2.同时使用fast和slow对链表进行遍历，直到fast或者fast.next为空;
- Step 3.当fast==null时，找了倒数第n+1个节点，此时slow的下一个节点就是要删除的节点；
- Step 4.当fast.next==null时，找了倒数第n个节点（也就是头节点），将head向下即可;
看不懂解释的话，直接看算法图解比较容易理解点
2.复杂度分析：
时间复杂度：O(L)，其中L是链表的长度。
空间复杂度：O(1)
3.算法图解
红色部分代表快指针fast，灰色部分代表慢指针slow（注：本人不会做成流程动画，希望会的朋友可以私信我指点一二，说个软件名字也可以，谢谢）
三、代码实现
每个代码块都写了注释，方便理解，代码还可以改进；
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode fast = head, slow = head; //先找出快指针的位置 for(int i = 0; i < n; i++) fast = fast.next; while(true){ if(fast == null)return head = head.next; else if(fast.next == null){ slow.next = slow.next.next; return head; } //同时移动两个指针 slow = slow.next; fast = fast.next; } } }
提交结果：
总结
以上就是今天要讲的内容，做题的时候发现寻找倒数第n个节点并删除，由于是单链表，所以需要找到倒数第n个节点的前驱结点才能删除，这样就可以把问题转变为寻找倒数第n个节点了，在利用滑动窗口的思路来移动快慢指针就可以了，所以就赶紧记录一下这时刻。
感谢观看，如果有帮助到你，请给题解点个赞和收藏，让更多的人看到。? ? ?
也欢迎你，关注我。? ? ?
原创不易，还希望各位大佬支持一下，你们的点赞、收藏和留言对我真的很重要！！！? ? ? 最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！
