牛客网新出了一个算法速刷 TOP101 题单，按照标签进行分类刷题，涵盖了链表、二分查找、排序、二叉树、堆、栈、队列、哈希、递归、回溯算法、动态规划、字符串、双指针、贪心算法、模拟算法等多个高频知识考点，准备校招、临时突击算法面试的同学可以根据这份题单进行系统的刷题。
题单地址：https://www.nowcoder.com/link/pc_kol_wsx
一、题目描述
给你一个链表，删除链表的倒数第 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 <= 300 <= Node.val <= 1001 <= n <= sz
二、题目解析
一般来说，链表相关的算法题考察的知识点有以下几个：
- 递归
- 反转
- 双指针
- 环
本题解题思路如下：
1、再原链表的前面添加一个虚拟头结点，使得原链表的头结点和其余的结点地位一样，进行删除操作时不需要进行区分处理。
2、在原链表的头部设置一个指针 former，使用 for 循环让它向后移动 n 步。
3、在原链表的头部再设置一个指针 cur，同时在虚拟头结点位置设置一个指针 latter。
4、接下来，同时让这三个指针向后移动，直到 former 指向了 null，此时 cur 指向的恰好就是倒数第 n 个结点。
5、由于 latter 一直在 cur 的上一个结点位置，这个时候只需要让 latter 指向 cur 的下一个结点，那么也就完成了删除 cur 结点的操作。
三、参考代码
// 本题文字版详解请访问下方网站
// https://www.algomooc.com
// 作者：程序员吴师兄
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
// 添加表头
ListNode dummy = new ListNode(-1);
dummy.next = head;
// 寻找需要删除的节点节点
ListNode cur = head;
// 指针 latter 指向虚拟头结点
ListNode latter = dummy;
ListNode former = head;
// 让 former 指针先向前走 n 步
for (int i = 0 ; i < n; i++) {
// former 指针向后移动
former = former.next;
}
// 接下来，让这两个指针 former 和 latter 同时向前移动，直到前指针 former 指向 NULL
while (former != null) {
// former 指针向后移动
former = former.next;
// latter 来到 cur 的位置
latter = cur;
// cur 指针向后移动
cur = cur.next;
}
// 删除 cur 这个位置的结点
latter.next = cur.next;
// 返回虚拟头结点的下一个结点
return dummy.next;
}
}
