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
进阶：你能尝试使用一趟扫描实现吗？
# V1-借助数组
## 思路
链表是单向的，但是需要从倒数第 N 个删除，那么如何知道整体的长度呢？
所以至少需要一次遍历。
我想到的最直接的思路，就是首先遍历一遍，把 ListNode 的所有节点存放在数组中。
这样可以获取倒对应的整体长度；
想删除的时候，直接 O(1) 获取对应的下标节点。
## java 实现
```java
/**
* 移除倒数的元素
*
* 个人认为这种接法是由于题目中的给出的2种解法的。
*
* leetcode 的2个解法实际上都是：length + (length-n) 次移动，这是不合理的。
* 如果 length=100，想移除倒数第一个元素，那么是遍历2次。
* 个人借助数组，则只需要 length+O(1) 的查找。
* 思路2：
* 构建双向链表，添加一个尾巴节点。
*
* @param head 头结点
* @param n 位数
* @return 结果
* @since v1
*/
public ListNode removeNthFromEnd(ListNode head, int n) {
List<ListNode> list = buildNodeList(head);
if(list.size() <= 1) {
return null;
}
// 考虑头尾的问题
// 如果是移除头结点
if(n == list.size()) {
// 第二个元素当做头结点
return list.get(1);
}
// 删除固定的节点
ListNode pre = list.get(list.size()-n-1);
pre.next = n >= list.size() ? null : pre.next.next;
return list.get(0);
}
/**
* 构建一个完整的数组
* @param head 头结点
* @return 结果
* @since v1
*/
private List<ListNode> buildNodeList(ListNode head) {
List<ListNode> list = new ArrayList<>();
list.add(head);
while (head.next != null) {
ListNode next = head.next;
list.add(next);
head = head.next;
}
return list;
}
效果
Runtime: 0 ms, faster than 100.00% of Java online submissions for Remove Nth Node From End of List.
Memory Usage: 37.9 MB, less than 30.88% of Java online submissions for Remove Nth Node From End of List.
当时因为效果太好，所以直接跳过了。
本文主要查缺补漏，把官方的几个解法都记录一下。
V2-两次遍历
官方解法
第一次，遍历整个链表，计算出长度 len。
第二次遍历，找到删除节点，执行删除。返回对应的头结点。
当然，为了避免处理麻烦，我们可以加一个 dummy 节点。
为了方便删除操作，我们可以从哑节点开始遍历 len - N + 1 个节点。
当遍历到第 len - N + 1 个节点时，它的下一个节点就是我们需要删除的节点，这样我们只需要修改一次指针，就能完成删除操作。
java 实现
/**
* 移除倒数的元素
*
* @param head 头结点
* @param n 位数
* @return 结果
*/
public ListNode removeNthFromEnd(ListNode head, int n) {
int len = getLen(head);
// 创建 dummy 节点
ListNode dummy = new ListNode(0, head);
ListNode cur = dummy;
for (int i = 1; i < len - n + 1; ++i) {
cur = cur.next;
}
// 删除 cur 节点
cur.next = cur.next.next;
return dummy.next;
}
/**
* 获取长度
* @param head 头结点
* @return 结果
*/
private int getLen(ListNode head) {
int i = 0;
while (head != null) {
head = head.next;
i++;
}
return i;
}
效果
Runtime: 0 ms, faster than 100.00% of Java online submissions for Remove Nth Node From End of List.
Memory Usage: 40.3 MB, less than 74.3% of Java online submissions for Remove Nth Node From End of List.
当然，严格来说，这个方法最差的复杂度实际上是遍历两遍。
比如 1W 个元素，删除最后一个，这样性能其实一般，只是测试用例区分性不强而已。
V3-双指针
思考
假设链表的长度为 L，我们希望倒数第 n 个元素，有没有办法避免 V2 的两次遍历呢?
我们可以定义两个指针 i, j。
i 先走 n 步，然后 i j 同时往后走。当 i 走到结尾的时候，此时 j 刚好就是在倒数第 n 个位置。
当然，为了处理方便。我们可以引入 dummy 节点，让 j 从 dummy 开始，i 从 head 开始。
java 实现
public ListNode removeNthFromEnd(ListNode head, int n) {
// 创建 dummy 节点
ListNode dummy = new ListNode(0, head);
// i 先走 n 步
ListNode i = head;
ListNode j = dummy;
for(int k = 0; k < n; k++) {
i = i.next;
}
// 二者同时开始走
while (i != null) {
j = j.next;
i = i.next;
}
// 删除当前节点
j.next = j.next.next;
// 返回
return dummy.next;
}
效果
Runtime: 0 ms, faster than 100.00% of Java online submissions for Remove Nth Node From End of List.
Memory Usage: 40.4 MB, less than 64.16% of Java online submissions for Remove Nth Node From End of List.
小结
官方的解法 1 实际上比较容易想到，不过需要两次遍历。
想避免这种两次遍历，有 2 种方式：
1）通过数组存储 listNode，避免再次遍历
2）通过双指针，达到一次满足的效果。
开源地址
为了便于大家学习，所有实现均已开源。欢迎 fork + star~
参考资料
https://leetcode.cn/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-b-61/
