LeetCode 19：删除链表的倒数第 N 个结点（Remove Nth Node From End of List）题解

Remove Nth Node From End of List 是 LeetCode Hot 100 里非常经典的一道链表题。

这道题的难点不在于代码有多长，而在于你能不能把“倒数第 N 个结点”这个描述，转换成一个容易处理的链表问题。很多人第一次做这道题时，会被“倒数”这两个字绕住，不知道应该从哪里下手。其实只要把链表长度算出来，这个问题就能立刻转化成“删除正数第几个结点”。

你给出的这份 Java 代码，就是一种非常稳、也非常容易理解的写法：

• 先遍历一遍链表，求出总长度

• 再计算出要删除的是正数第几个位置

• 最后再遍历到前一个结点，完成删除

这也是这道题非常经典的一种解法。本文就结合这段代码，系统地讲一下这道题的思路。

题目介绍

给你一个链表，要求删除链表的倒数第 n 个结点，并返回删除后的头结点。

例如链表是：

1 -> 2 -> 3 -> 4 -> 5

如果：

n = 2

那么倒数第 2 个结点就是 4，删除之后链表变成：

1 -> 2 -> 3 -> 5

注意，题目要求删除的是 倒数第 n 个结点，而不是值等于 n 的结点。

这两个概念一定不能混淆。

示例

示例 1

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

链表长度为 5，倒数第 2 个结点就是正数第 4 个结点，也就是值为 4 的结点。

示例 2

输入：head = [1], n = 1
输出：[]

链表中只有一个结点，删除倒数第 1 个结点之后，链表就变成空链表。

示例 3

输入：head = [1,2], n = 1
输出：[1]

倒数第 1 个结点就是最后一个结点，也就是值为 2 的结点，删除之后只剩下 1。

最直接的思路

这道题如果不去强行想“双指针一次遍历”，其实最容易想到的方法就是：

1. 先遍历一遍链表，求出总长度 length

2. 倒数第 n 个结点，其实就是正数第 length - n + 1 个结点

3. 删除某个结点时，一般不直接操作它自己，而是找到它的前一个结点

4. 修改前一个结点的 next 指针即可完成删除

这个思路非常自然，也很好理解。

而你这段代码就是按照这个逻辑实现的。

Java 代码

下面是你给出的代码，我这里保留原有逻辑，并加上注释方便理解：

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;
        }
​
        // 要删除的结点前一个位置，需要走到下标 length - n 的位置
        int index = length - n;
        current = dummy;
​
        // 走到待删除结点的前一个结点
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
​
        // 删除结点
        current.next = current.next.next;
​
        return dummy.next;
    }
}

解题思路拆解

这段代码不长，但链表题往往难在细节上。 下面我们一步一步来看。

1. 为什么要创建 dummy 哑结点？

ListNode dummy = new ListNode(0);
dummy.next = head;

这是链表题里一个非常常见的技巧。

因为删除结点时，我们通常需要找到“待删除结点的前一个结点”。 但如果要删除的是头结点，那么它是没有前驱的，这时候代码就会变得比较麻烦。

比如：

head = [1]
n = 1

这时候要删除的就是头结点本身。 如果没有 dummy，你就得单独写分支判断。

而有了 dummy 之后，链表就可以看成：

dummy -> 1 -> 2 -> 3 ...

这样即使删除的是原来的头结点，我们也依然能通过修改：

dummy.next

来完成操作。

所以引入哑结点，本质上是为了统一逻辑，减少边界判断。

2. 为什么先求链表长度？

int length = 0;
ListNode current = head;
while (current != null) {
    length++;
    current = current.next;
}

因为题目给的是“倒数第 n 个结点”，而链表本身不支持随机访问，我们无法一下子定位到它。

所以最直接的做法就是先数出链表一共有多少个结点。

假设链表总长度是：

length

那么倒数第 n 个结点，其实就是正数第：

length - n + 1

个结点。

而如果我们想删除它，就需要找到它前一个结点，也就是正数第：

length - n

个结点。

这就是下面这句代码的来源：

int index = length - n;

3. 为什么从 dummy 开始走？

current = dummy;
for (int i = 0; i < index; i++) {
    current = current.next;
}

因为这里要找到的是“待删除结点的前一个结点”。

在引入 dummy 之后，链表的起点就变成了 dummy。 这时候如果 index = 0，就表示要删除的其实是原链表头结点，那么前驱正好就是 dummy。

这种写法能自然覆盖所有情况。

举个例子：

情况 1：删除头结点

head = [1,2,3], n = 3

链表长度 length = 3，所以：

index = length - n = 0

此时 current 不需要往后走，仍然停在 dummy。 然后执行：

current.next = current.next.next;

就等价于：

dummy.next = head.next;

也就是删除头结点。

情况 2：删除中间结点

head = [1,2,3,4,5], n = 2

链表长度为 5，所以：

index = 5 - 2 = 3

从 dummy 开始走 3 步，会停在值为 3 的结点上。 接下来删掉它后面的 4，正好符合题意。

4. 删除操作为什么只需要一行？

current.next = current.next.next;

这就是链表删除结点的核心操作。

假设当前链表是：

1 -> 2 -> 3 -> 4 -> 5

如果当前 current 指向的是值为 3 的结点，那么：

• current.next 是 4

• current.next.next 是 5

执行完：

current.next = current.next.next;

之后，链表就变成：

1 -> 2 -> 3 -> 5

原来的结点 4 就被跳过去了，相当于被删除。

在 Java 中，后续没有引用指向这个结点，它最终会被垃圾回收。

手动模拟一遍

我们用经典样例来走一遍流程：

head = [1,2,3,4,5], n = 2

第一步：统计长度

遍历链表后得到：

length = 5

第二步：计算前驱位置

index = length - n = 5 - 2 = 3

这表示要找到待删除结点前面的那个结点，也就是从 dummy 开始走 3 步。

链表结构可以看成：

dummy -> 1 -> 2 -> 3 -> 4 -> 5

从 dummy 出发：

• 走 1 步到 1

• 走 2 步到 2

• 走 3 步到 3

所以此时 current 指向值为 3 的结点。

第三步：删除结点

执行：

current.next = current.next.next;

也就是把：

3 -> 4 -> 5

改成：

3 -> 5

最终链表变成：

1 -> 2 -> 3 -> 5

复杂度分析

时间复杂度

这段代码总共遍历了链表两次：

1. 第一次求长度

2. 第二次定位待删除结点的前驱

所以时间复杂度是：

O(n)

虽然看起来是两次遍历，但常数项不影响大方向，整体仍然是线性时间复杂度。

空间复杂度

只使用了少量额外变量：

• dummy

• current

• length

• index

所以空间复杂度是：

O(1)

这道题的关键点在哪里？

这道题真正容易让人卡住的地方，其实有两个：

第一，倒数如何转换成正数位置

这是思维转换的关键。

倒数第 n 个结点 = 正数第 length - n + 1 个结点

而我们真正要找的是它前一个结点，所以位置是：

length - n

第二，删除头结点怎么处理

如果没有 dummy，删除头结点会比较麻烦，需要单独分类讨论。 而一旦有了哑结点，整道题就会顺很多。

所以这题看似简单，实际上非常适合训练你对链表边界情况的处理能力。

这道题还有更优雅的写法吗？

有。

这道题还有一种非常经典的写法是：

快慢指针 / 双指针

思路是让快指针先走 n 步，然后快慢指针一起走；当快指针走到链表末尾时，慢指针刚好停在待删除结点的前一个位置。

这种方法可以做到只遍历一遍链表。

不过从理解难度上来说，你这份“两次遍历求长度”的代码其实更直观，也更适合初学者掌握。 在面试或者刷题初期，能先把这种稳定写法吃透，其实已经非常好了。

总结

这道题的核心思路其实很清楚：

1. 先统计链表长度

2. 把“倒数第 n 个结点”转换成“正数第几个结点”

3. 借助 dummy 统一删除逻辑

4. 找到前驱结点后，修改指针完成删除

所以这道题虽然是链表题，但本质上考察的是两件事：

• 你能不能完成“倒数位置”的转换

• 你会不会用哑结点处理链表边界

这是一道非常典型的链表基础题。 如果你刚开始刷链表，建议一定要把这道题真正理解透，尤其是 dummy 的作用和删除操作的本质。

因为后面很多链表题，比如：

• 删除链表中的某个结点

• 合并两个有序链表

• 反转链表的一部分

• 两两交换链表中的结点

都会反复用到类似的思想。

把这道题吃透之后，你对链表指针操作的感觉会明显更扎实。