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

更新: 7/5/2026 字数: 0 字 时长: 0 分钟

题目描述

给你一个链表的头节点 head,请你删除链表的倒数第 n 个结点,并返回删除后链表的头节点。

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
解释：倒数第 2 个是节点 4，删除它

边界示例:

输入：head = [1], n = 1        输出：[]        // 删掉唯一节点
输入：head = [1,2], n = 2      输出：[2]       // 删掉的是头节点

难点在于"倒数"。链表只能从头往后走,无法直接跳到"倒数第 n 个"。而且要删除一个节点,必须拿到它的前驱。这两个约束决定了解法的方向。

思路拆解

暴力解法:两趟遍历

最直觉的想法:先遍历一趟数出链表总长 ,那么倒数第 个就是正数第 个;再遍历一趟走到它的前驱,改指针删除。

点击展开两趟遍历解法（可行，但需两趟）

function removeNthFromEnd(head, n) {
  const dummy = new ListNode(0, head);

  // 第一趟：数长度
  let len = 0;
  for (let node = head; node; node = node.next) len++;

  // 第二趟：走到待删节点的前驱（正数第 len - n 个之后）
  let prev = dummy;
  for (let i = 0; i < len - n; i++) prev = prev.next;

  prev.next = prev.next.next; // 跳过待删节点
  return dummy.next;
}

两趟遍历有什么不足？

它正确且好懂,时间也是 ,但需要遍历两趟。面试常追问"能否只用一趟?"——这就引出了快慢双指针。真正的优化点不是复杂度量级,而是只扫一遍链表(数据流场景下尤其重要,你可能无法回头重数)。

最优解法:快慢双指针(一趟遍历)

核心洞察:让两个指针保持恰好 n 步的固定间隔一起往前走。当快指针到达末尾时,慢指针正好停在待删节点的前驱上。

核心思路

1. 建哑节点 dummy 指向 head(关键!这样"删除头节点"也统一成"删除某节点的后继");
2. fast 与 slow 都从 dummy 出发;
3. 先让 fast 独自走 n 步,此时两者间隔为 ;
4. 然后 fast、slow 同速前进,直到 fast.next === null(fast 到达最后一个节点);
5. 此时 slow 恰好是倒数第 个节点的前驱,执行 slow.next = slow.next.next 删除;
6. 返回 dummy.next。

为什么间隔 就对? 设链表长 。fast 先走 步后,它到末尾还需走 步;slow 同步走这 步后,位置正是第 个节点(以 dummy 为第 0 个),它的后继就是第 个 = 倒数第 个。用等式表示:

交互式动画演示

下面用样例 head = [1,2,3,4,5]、n = 2 演示快慢双指针一趟解法的完整过程。点击 下一步 观察 fast 先走 n 步、两指针同速前进、最后 slow 停在前驱并删除节点:

步骤 1 / 9初始化n = 2

fastslow

D

→

1

→

2

→

3

→

4

→

5

→

null

初始化：在头节点前加哑节点 dummy。fast 和 slow 都从 dummy 出发（间隔为 0）。n = 2，目标删除倒数第 2 个节点。

完整代码(JavaScript)

高亮行为快慢指针的三个关键动作:先行 n 步、同速前进、删除。

/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
function removeNthFromEnd(head, n) {
  const dummy = new ListNode(0, head); // 哑节点，统一删头节点的情况
  let fast = dummy;
  let slow = dummy;

  // 1. fast 先独自走 n 步，制造 n 步间隔
  for (let i = 0; i < n; i++) {
    fast = fast.next;
  }

  // 2. 两指针同速前进，直到 fast 到达最后一个节点
  while (fast.next !== null) {
    fast = fast.next;
    slow = slow.next;
  }

  // 3. 此时 slow 是待删节点的前驱，跳过它
  slow.next = slow.next.next;

  return dummy.next; // 用哑节点的 next 返回，兼容删头场景
}

复杂度分析

设链表长度为 。

解法	时间复杂度	空间复杂度	遍历趟数	说明
两趟遍历			2	先数长度,再走到前驱
栈辅助			1	全部入栈,弹 次找前驱
快慢双指针			1	一趟完成,间隔 定位

边界与易错点

常见踩坑

1. 不用哑节点删头节点会翻车:当要删的是头节点(如 [1,2], n=2)时,它没有前驱。哑节点让 slow 有落脚点,dummy.next 也能正确返回新头。这是本题最关键的技巧。
2. fast 先走 n 步还是 n+1 步? 取决于起点。本文让 fast、slow 都从 dummy 出发、fast 走 n 步、循环条件 fast.next !== null——这套组合能让 slow 精准停在前驱。若让两者从 head 出发,则需相应调整,极易差一位(off-by-one)。建议固定记住"都从 dummy 出发 + 先走 n 步 + fast.next 判空"这一套。
3. 循环条件写成 fast !== null:那样 slow 会多走一步,停到待删节点本身而非前驱,导致删错。
4. n 等于链表长度:即删头节点,上面的写法天然覆盖。
5. 假设 n 合法:题目保证 ,无需额外校验;但工程代码中建议对越界做防御。

简易解题思路(记忆口诀)

一句话记忆:「哑头开路,快跑 N 步,一起前进,慢删后继」

把它想象成两个人拉一根固定长度为 N 的绳子走路:

• 哑头开路:先在真头前面加个"假节点"(dummy),这样连头节点都能被安全删除;
• 快跑 N 步:让快指针先冲出去 N 步,拉开正好 N 的间距;
• 一起前进:两人保持这根"N 步长的绳子"同速走,快的一撞到墙(链表尾)就停;
• 慢删后继:此刻慢指针正好卡在"要删的那个"前一格,一句 slow.next = slow.next.next 把它跳过去。

四句话口诀:哑头开路 → 快跑 N 步 → 一起前进 → 慢删后继。 记住核心画面:"绳子长度 = N,快指针撞墙时,慢指针就在待删节点前面。"