19. 删除链表的倒数第 N 个节点 (Medium)
专题归类： 04-链表 LeetCode 链接： https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给你一个链表，删除链表的倒数第 n 个节点，并返回链表的头节点。
示例：
- 输入：head = [1,2,3,4,5], n = 2
- 输出：[1,2,3,5]
- 解释：删除倒数第 2 个节点（值为 4）
题目详细分析
- 数据范围： 链表中节点数在 [1, 30] 范围内，n 保证是有效的（1 ≤ n ≤ 链表长度）
- 输入特征： 单链表，只能从头到尾遍历。n 从 1 开始计数（倒数第 1 个是尾节点）
- 核心约束： 只能一次遍历完成（进阶要求），不能先遍历算长度再删
- 隐藏条件： 删除节点需要找到待删节点的前一个节点。删除头节点时没有前驱，需要特殊处理
- 边界条件： 删除头节点（n = 链表长度）、删除尾节点（n = 1）、链表只有一个节点
小白版直白理解
就像你不知道一列火车有多长，但想知道从车尾往前数的第 n 节车厢是哪个，然后把它去掉。
一个聪明的办法：找两个朋友，让第一个朋友先往前多走 n 步（提前出发），然后两个朋友以相同速度往前走。当第一个朋友走到车尾时，第二个朋友正好站在待删车厢的前一节。因为第一个朋友提前走了 n 步，所以第二个朋友距离车尾正好还有 n 步。
为了防止删的是车头（第一节车厢），我们在火车前面加一个虚拟的「第 0 节车厢」，这样不管删哪节都有前驱。
解题思路
思路一：快慢指针 + 虚拟头节点（推荐）
为什么这样想： 要找到倒数第 n 个节点，本质是找到距离末尾 n 步的节点。但单链表不知道末尾在哪里。让快指针先走 n+1 步（指向倒数第 n 个节点的前一个），然后两个指针同步走直到快指针到末尾，此时慢指针就停在待删节点的前一个位置。
关键洞察： 快指针先走 n+1 步而不是 n 步，是为了让慢指针指向待删节点的前驱，这样才能执行删除操作。
def removeNthFromEnd(head, n):
"""快慢指针 + 虚拟头节点"""
dummy = ListNode(0, head) # 虚拟头节点，防止删除头节点时出问题
fast = slow = dummy
# 快指针先走 n+1 步
for _ in range(n + 1):
fast = fast.next
# 快慢指针同步前进
while fast:
fast = fast.next
slow = slow.next
# 此时 slow 指向待删节点的前驱
slow.next = slow.next.next
return dummy.next思路二：两次遍历法
思路讲解： 先遍历一次链表计算出总长度 L，则倒数第 n 个节点就是正数第 L-n+1 个。第二次遍历到第 L-n 个节点（待删节点的前驱）执行删除。思路简单但需要两次遍历。
def removeNthFromEnd(head, n):
"""两次遍历法"""
# 第一次遍历：计算长度
length = 0
cur = head
while cur:
length += 1
cur = cur.next
# 虚拟头节点
dummy = ListNode(0, head)
cur = dummy
# 第二次遍历：走到待删节点的前驱
for _ in range(length - n):
cur = cur.next
cur.next = cur.next.next
return dummy.next思路三：栈辅助法
思路讲解： 遍历链表将所有节点入栈，然后弹出 n 个节点，此时栈顶就是待删节点的前驱。用虚拟头节点统一处理删除头节点的情况。
def removeNthFromEnd(head, n):
"""栈辅助法"""
dummy = ListNode(0, head)
cur = dummy
stack = []
while cur:
stack.append(cur)
cur = cur.next
# 弹出 n 个节点
for _ in range(n):
stack.pop()
# 栈顶就是待删节点的前驱
prev = stack[-1]
prev.next = prev.next.next
return dummy.next易错点
- 快指针先走 n+1 步： 如果走了 n 步，慢指针就指向待删节点本身而不是前驱，无法执行删除
- 虚拟头节点： 删除头节点时，如果没有 dummy，
head = head.next可以，但代码需要分支处理。用 dummy 可以统一逻辑 - n 的合法性： 题目保证 n 有效，但通用代码应考虑 n 是否超过链表长度
- dummy 初始连接：
dummy = ListNode(0, head)不能漏掉 head 参数，否则 dummy 与链表断开 - 返回值： 始终返回
dummy.next，而不是 head（head 可能已被删除）
框架提炼
快慢指针找倒数第 N 个模板： 适用于查找或删除链表倒数第 N 个节点的场景。
def find_nth_from_end(head, n):
"""找到倒数第 n 个节点"""
fast = slow = head
for _ in range(n):
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
return slow删除操作加强版（带虚拟头节点）：
def remove_nth_from_end(head, n):
dummy = ListNode(0, head)
fast = slow = dummy
for _ in range(n + 1):
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.next快慢指针固定偏移量这一技巧可推广到更多需要「定位到距离末尾固定距离」的场景。
关联题目
- 141-环形链表 — 快慢指针的基础应用
- 206-反转链表 — 另一种基础链表操作
- 876-链表的中间结点 — 快慢指针找中点，是另一种固定步差的应用