算法

删除链表的倒数第 N 个结点

loser

22 Aug 2026 • 7 min read

给你一个链表的头节点 head，删除链表的倒数第 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

进阶：

你能尝试使用一趟扫描实现吗？

解法一（计算链表长度）：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int length = 0;
        ListNode* cur = head;

        while (cur != nullptr)
        {
            length++;
            cur = cur->next;
        }

        ListNode dummy(0, head);
        ListNode* prev = &dummy;

        for (int i = 0; i < length - n; i++)
        {
            prev = prev->next;
        }

        prev->next = prev->next->next;

        return dummy.next;
    }
};

解法二（快慢指针一趟扫描）：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode dummy(0, head);

        ListNode* fast = &dummy;
        ListNode* slow = &dummy;

        for (int i = 0; i < n; i++)
        {
            fast = fast->next;
        }

        while (fast->next != nullptr)
        {
            fast = fast->next;
            slow = slow->next;
        }

        slow->next = slow->next->next;

        return dummy.next;
    }
};

核心思想

这题要删除倒数第 n 个结点。

如果知道链表长度 length，倒数第 n 个结点就是正数第：

length - n + 1

个结点。

但删除一个链表结点时，真正需要找到的是它的前一个结点。

因为要修改的是：

prev->next

所以如果用长度法，需要先遍历链表求长度，再从头走到待删除结点的前一个位置。

进阶要求一趟扫描，可以使用快慢指针。

这题最关键的观察是：

让快指针先走 n 步，然后快慢指针一起走；当快指针到达尾结点时，慢指针正好停在待删除结点的前一个结点。

为什么需要虚拟头节点

如果要删除的结点刚好是头节点，例如：

head = [1], n = 1

删除之后应该返回空链表。

又例如：

head = [1,2], n = 2

删除倒数第 2 个结点，也就是删除头节点 1。

如果没有虚拟头节点，删除头节点需要单独处理。

使用：

ListNode dummy(0, head);

让 dummy 指向原来的头节点。

这样即使删除的是头节点，也可以统一写成：

slow->next = slow->next->next;

最后返回：

dummy.next

就是删除后的新头节点。

解法一：计算链表长度

先遍历一遍链表，得到链表长度 length。

如果要删除倒数第 n 个结点，那么它前面有：

length - n

个结点。

所以从虚拟头节点 dummy 出发，向后走 length - n 步，就会到达待删除结点的前一个结点。

代码是：

for (int i = 0; i < length - n; i++)
{
    prev = prev->next;
}

然后删除：

prev->next = prev->next->next;

这个方法简单直观，但需要两次遍历。

解法二：快慢指针一趟扫描

为了只扫描一趟，可以让两个指针之间保持固定距离。

初始时：

ListNode* fast = &dummy;
ListNode* slow = &dummy;

先让 fast 走 n 步：

for (int i = 0; i < n; i++)
{
    fast = fast->next;
}

此时 fast 和 slow 之间相隔 n 个结点。

接下来让它们一起向后走：

while (fast->next != nullptr)
{
    fast = fast->next;
    slow = slow->next;
}

当 fast 到达尾结点时，slow 正好在倒数第 n 个结点的前一个位置。

这时删除 slow->next 即可。

为什么 `slow` 会停在待删除结点的前一个位置

快指针先走了 n 步，所以 fast 和 slow 之间始终相隔 n 个结点。

当 fast 停在最后一个结点时，从 fast 到链表末尾已经没有后续结点。

此时从 slow->next 到链表末尾，正好有 n 个结点。

也就是说：

slow->next

就是倒数第 n 个结点。

所以 slow 正好是待删除结点的前一个结点。

删除操作就是：

slow->next = slow->next->next;

边界情况

如果链表只有一个结点：

head = [1], n = 1

虚拟头节点的 next 指向 1。

快指针先走 1 步后到达原头节点。

此时 fast->next == nullptr，循环不执行。

slow 仍然在 dummy 上，删除 slow->next 后，dummy.next 变成 nullptr。

返回空链表，正确。

如果删除的是尾结点，例如：

head = [1,2], n = 1

快指针先走到结点 1。

快慢指针一起走，直到 fast 到达结点 2。

此时 slow 在结点 1，删除 slow->next，结果是 [1]。

如果删除的是头节点，例如：

head = [1,2], n = 2

快指针先走到结点 2，循环不执行。

slow 仍然在 dummy 上，删除原头节点后返回 [2]。

正确性证明

我们证明：快慢指针解法能够正确删除链表的倒数第 n 个结点。

结论 1：快指针先走 `n` 步后，`fast` 和 `slow` 之间相隔 `n` 个结点

初始时，fast 和 slow 都指向虚拟头节点 dummy。

执行：

for (int i = 0; i < n; i++)
{
    fast = fast->next;
}

之后，fast 比 slow 多走了 n 步。

所以二者之间相隔 n 个结点。

结论 2：一起移动时，这个距离保持不变

在循环中：

fast = fast->next;
slow = slow->next;

两个指针每次都向后移动一步。

因此 fast 和 slow 之间的距离始终保持为 n 个结点。

结论 3：当 `fast` 到达尾结点时，`slow->next` 是倒数第 `n` 个结点

循环结束条件是：

fast->next == nullptr

这说明 fast 位于链表最后一个结点。

根据结论 2，fast 和 slow 之间相隔 n 个结点。

因此从 slow->next 开始到链表末尾，正好有 n 个结点。

所以 slow->next 就是倒数第 n 个结点。

结论 4：删除 `slow->next` 后，链表正好少了目标结点

根据结论 3，slow->next 是要删除的结点。

执行：

slow->next = slow->next->next;

会让 slow 直接指向目标结点的后一个结点。

因此目标结点被从链表中跳过，其余结点的相对顺序不变。

得出结论

由结论 1 和结论 2 可知，快慢指针之间始终保持正确距离。

由结论 3 可知，循环结束时 slow->next 正好是倒数第 n 个结点。

由结论 4 可知，删除操作正确移除了目标结点，并保留了其它结点顺序。

因此算法正确。

举例理解

以：

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

为例。

加入虚拟头节点后：

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

先让 fast 走 2 步：

slow = dummy
fast = 2

然后快慢指针一起走，直到 fast 到达尾结点：

slow = 3
fast = 5

此时 slow->next 是结点 4。

删除它：

1 -> 2 -> 3 -> 5

返回结果：

[1,2,3,5]

复杂度分析

解法一

先遍历链表求长度，再遍历到待删除结点的前一个位置。

时间复杂度：O(n)
空间复杂度：O(1)

解法二

快慢指针只需要一趟扫描。

时间复杂度：O(n)
空间复杂度：O(1)

解法二满足进阶要求，是更推荐的做法。