力扣-19. 删除链表的倒数第N个节点（Remove Nth Node From End of List）

最后编辑于2025-07-04

19. 删除链表的倒数第 N 个节点（Remove Nth Node From End of List）

Medium

给定链表的头结点 head，删除链表的倒数第 n 个节点，并返回链表的头结点。

示例：

alt text

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

约束：

  • 链表长度 sz 满足 1 <= sz <= 30。
  • 0 <= Node.val <= 100。
  • 1 <= n <= sz。

进阶（Follow up）： 是否可以一次遍历完成？

思路与实现（双指针，单次遍历）

要求一次遍历完成删除倒数第 n 个节点，常用做法是 双指针（快慢指针）：

  1. 设定两个指针 fast 和 slow，都指向链表头（或使用哨兵节点简化边界情况）。
  2. 先让 fast 向前走 n 步。此时如果 fast 为 nullptr，说明要删除的是头结点，直接返回 head->next 即可（或使用哨兵节点更统一）。
  3. 然后同时移动 fast 和 slow，直到 fast 到达链表末尾。此时 slow 指向的是要删除节点的前驱节点（即 slow->next 是目标节点）。
  4. 调整指针 slow->next = slow->next->next 完成删除，返回头结点（若使用哨兵返回 dummy.next）。

使用哨兵（dummy）节点可以统一处理删除头结点等边界情况，代码更整洁。

C++ 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode* fast = &dummy;
        ListNode* slow = &dummy;
        // fast 先走 n 步（走到比 slow 多 n 个节点）
        for (int i = 0; i < n; ++i) fast = fast->next;
        // 再同时走，直到 fast 到达链表末尾
        while (fast->next) {
            fast = fast->next;
            slow = slow->next;
        }
        // slow->next 即为需删除节点
        ListNode* toDelete = slow->next;
        slow->next = slow->next->next;
        // 可选：释放 toDelete
        // delete toDelete;
        return dummy.next;
    }
};
  • 时间复杂度： O(sz)（单次遍历）
  • 空间复杂度： O(1)

作者想说的话：
使用哨兵节点能把头结点被删除的特殊情况纳入统一处理，双指针（快慢）先让快指针领先 n 步再同步前进，最终慢指针正好停在待删除节点的前驱位置，单次遍历即可完成任务，代码简洁且稳健。