LeetCode 19. 删除链表的倒数第 N 个节点

题目描述

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

这题是链表双指针的经典题，核心难点在于：如何在一次遍历中定位到“待删除节点的前一个节点”。

解题思路：虚拟头节点 + 快慢指针

为了统一处理“删除头结点”这种边界情况，先创建一个虚拟头节点 dummy，让 dummy->next = head。

然后定义两个指针：

  1. fast 和 slow 都从 dummy 出发。
  2. 先让 fast 走 n + 1 步，这样 fast 和 slow 之间就保持 n + 1 的间距。
  3. 接着 fast 和 slow 同时向后移动，直到 fast 走到 nullptr。
  4. 此时 slow 正好停在“倒数第 个节点的前一个节点”，执行删除即可：slow->next = slow->next->next。

为什么是 n + 1？

  • 因为我们要拿到的是“前驱节点”，不是目标节点本身。
  • 多走这 1 步，能让 slow 最终停在正确位置。

代码实现（C++）

/**
 * 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 = new ListNode(0, head);
    ListNode *fast = dummy;
    ListNode *slow = dummy;

    // fast 先走 n + 1 步，让 slow 停在待删除节点的前一个位置
    ++n;
    while (n-- && fast != nullptr) {
      fast = fast->next;
    }

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

    slow->next = slow->next->next;
    return dummy->next;
  }
};

复杂度分析

  • 时间复杂度：，其中 为链表长度，只遍历一次链表。
  • 空间复杂度：，只使用了常数级额外空间。

小结

这题的关键是两个点：虚拟头节点处理边界、快慢指针维护固定间距。掌握了这套思路后，很多链表“删除/定位倒数第 个节点”的题都可以直接套用，属于非常值得反复练习的模板题。