19、删除链表的倒数第N个节点
19、删除链表的倒数第 N 个节点
题意
给你一个链表，删除链表的倒数第 n 个节点，并且返回链表的头节点。
难度
中等
示例
示例 1：
019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6
%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9-20240131111417.png
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
输入：head = [1,2], n = 1
输出：[1]
进阶：你能尝试使用一趟扫描实现吗？
分析
看到这道题，其实很容易想到 LinkedList 的 remove 方法，对吧？知道 remove 方法是如
何实现的，就能写出这道题的题解。
019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6
%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9-20240131132502.png
我也曾在《二哥的 Java 进阶之路》上讲过 remove 方法的源码，其实现方式也非常简单，
先遍历找到对应的节点，通过 node 方法实现，内核用的是 for 循环。
019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6
%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9-20240131132904.png
找到节点后，将节点的前一个节点的 next 指向节点的下一个节点；将节点的下一个节点
的 prev 指向节点的前一个节点，这样就将节点从链表中删除了。
019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6
%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9-20240131133704.png
也就是前面提到的 unlink 方法。
LinkedList 其实比 LeetCode 这道链表的题复杂，因为 LinkedList 是双向链表，而
LeetCode 这道题是单向链表，下面是 LeetCode 为我们定义的链表 ListNode。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
*}
*/
把注释去掉大概就是这样子：
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
两个属性，或者叫成员变量、字段，一个是 val，一个是 next，val 是当前节点的值，next
是下一个节点的引用。
三个构造方法，一个是无参构造方法，一个是只有 val 的构造方法，一个是 val 和 next 的
构造方法。
单向链表的结构就相对简单，只有 next 没有 prev。
019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6
%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9-20240131134252.png
讲到这里，大家应该就能写出题解了。
第一步，遍历链表，找出链表的长度，确定要删除的节点的位置。
int length = 0;
ListNode current = head;
while (current != null) {
length++;
current = current.next;
}
// 找到要删除节点的前一个节点
int index = length - n;
注意是倒数第 n 个节点，所以要用链表的长度减去 n。倒数第 4 个节点的前一个节点就是
5-4=1，也就是第一个节点。
019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6
%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9-20240131140446.png
第二步，遍历链表，找到要删除节点的前一个节点。
为了方便删除节点，我们需要一个虚拟节点，让虚拟节点的 next 指向 head，这样就能保
证删除节点的前一个节点不为空。
ListNode dummy = new ListNode(0);
dummy.next = head;
为什么？
因为当需要删除的是头节点时，操作与删除中间节点略有不同，因为没有前一个节点可以
引用。引入虚拟头节点后，删除头节点和其他节点的操作可以统一处理，因为头节点也会
有一个前节点（即虚拟头节点）。
当增加了虚拟节点后，要删除节点的前一个节点就是 index。
019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6
%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9-20240131142556.png
current = dummy;
for (int i = 0; i < index; i++) {
current = current.next;
}
第三步，找到节点后删除。
current.next = current.next.next;
也就是把要删除节点的前一个节点（current）的 next 指向要删除节点（current.next）
的下一个节点（current.next.next）。
第四步，返回虚拟节点的 next。
return dummy.next;
019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6
%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9-20240131143040.png
OK，来看完整的题解：
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
// 创建一个虚拟头节点，简化边界条件处理
ListNode dummy = new ListNode(0);
dummy.next = head;
// 第一次遍历，计算链表的总长度
int length = 0;
ListNode current = head;
while (current != null) {
length++;
current = current.next;
}
// 设置长度为到达要删除的节点的前一个节点
int index = length - n;
current = dummy;
// 第二次遍历，找到要删除的节点的前一个节点
for (int i = 0; i < index; i++) {
current = current.next;
}
// 删除节点，即跳过要删除的节点
current.next = current.next.next;
return dummy.next;
}
}
来看一下题解的效率，beat 100%了：
019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6
%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9-20240131143336.png
很不错，如果还不理解的话，那么可以 debug 一下 ACM 模式的代码，看看每一步的执行
过程。
class Main01801 {
public static void main(String[] args) {
Solution01801 solution = new Solution01801();
ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new
ListNode(4, new ListNode(5)))));
ListNode ans = solution.removeNthFromEnd(head, 4);
System.out.println(ans);
}
}
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution01801 {
public ListNode removeNthFromEnd(ListNode head, int n) {
// 创建一个虚拟头节点，简化边界条件处理
ListNode dummy = new ListNode(0);
dummy.next = head;
// 第一次遍历，计算链表的总长度
int length = 0;
ListNode current = head;
while (current != null) {
length++;
current = current.next;
}
// 设置长度为到达要删除的节点的前一个节点
int index = length - n;
current = dummy;
// 第二次遍历，找到要删除的节点的前一个节点
for (int i = 0; i < index; i++) {
current = current.next;
}
// 删除节点，即跳过要删除的节点
current.next = current.next.next;
return dummy.next;
}
}
总结
链表是除了数组之外，我们接触到的另外一个数据结构，对于它的增删改查，我们必须得
了如指掌，因为这俩数据结构是计算机用来存储数据单元的最基本的容器之二。
如果对链表比较陌生的话，一定要回头再看一下我在《二哥的 Java 进阶之路》中对
LinkedList 的讲解。
• LinkedList
尤其是链表的正删改查源码，一定要掌握。当然了，这道题对理解链表的结构和删除，也
会有很大的帮助。
力扣链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/