- 题目描述
- 解题分析
- 双指针
- 解题代码
- 递归
- 解题代码
- 总结
emmm，虽然我还不是程序员，但是你们是啊，大家注意保养身体，每天快乐加倍！
题目描述难度：中等
给你一个链表，删除链表的倒数第 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解题分析
题目要求遍历一遍就删除节点，我们可以使用双指针或者递归来完成。
双指针初始化两个指针 i j 此时它们都指向第一个节点，由于题目要求删除链表的倒数第 n 个结点，我们可以让 j 先往链表的尾部跑 n 个单位 ，此时有 j - i = n；我们让 i j 同时向后位移，这样在 j 碰到链表尾部节点之后，i 即为需要删除的节点的父节点。
比如示例1中 n = 2，则 j 向后遍历两个单位，此时 j = 3 ，i = 1，j - i = n 成立，当 j 遍历到最后一个节点 5 时，此时 i 代表节点 3 ，那么 i 的下一节点 4 即为需要删除的节点。
在 j 向后遍历 n 个单位时，会出现的情况有两种：
① j 顺利向后遍历了 n 个单位，此时 j - i = n；
② j 向后遍历了 n - 1 个单位后，在遍历第 n 个单位时发现该节点为 null；
对于这两种情况，当发生第二种情况时，则说明 n 的值为链表所有节点个数，即我们需要删除头部节点；
当发生第一种情况时，我们只需将两个指针同时向后挪动，直至 j 的下一节点为空，此时 i 所代表的节点的下一节点即为需要删除的节点，直接删除即可。
public ListNode removeNthFromEnd3(ListNode head, int n) {
ListNode i = head , j = head; // 初始化头部
while(n-- > 0){ // j 向后遍历 n 个单位
j = j.next;
}
if(j == null) return i.next; // 第二种情况发生，即 n = 所有节点个数
while(j.next != null){ // 同时位移 i 和 j 直至 j的下一节点为 null
i = i.next;
j = j.next;
}
i.next = i.next.next;
return head;
}
递归
递归比较难以理解，我也是歪打正着，大致就是先初始化一个计数器，然后对链表进行探底，探底后挨个节点回退，每次回退一个节点，计数器加一，直到回退到 需要删除的节点的父节点，再将需要删除的节点删除。
解题代码
int cur = 0; // 计数器
public ListNode removeNthFromEnd(ListNode head, int n){
remove(head , n);
return cur == n ? head.next : head; // cur 等于 n 代表需要删除根节点
}
public ListNode remove(ListNode head, int n) {
if(head == null) return head; // 探底后回退
ListNode next = remove(head.next , n); // 拿到下一节点
if(cur++ == n) head.next = next.next; // 进入if时 head是需要删除的节点的父节点
return head;
}
总结
我最开始解题是利用栈来写的，后来效率低到只超过了 8% ， 直接反手看了一波别人的题解，发现了双指针和递归的写法，双指针是一看就会，递归是完全瞎摸索出来的。
看到了别人说的一句话，顺手记录一下：只有多做题那些解题模板才会出现在脑海里面。
再接再厉！
岁月悠悠，衰微只及肌肤；热忱抛却，颓废必致灵魂
