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

题目描述

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

示例

示例 1：

示例 2：

示例 3：

约束条件

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

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

我的解题思路

链表只能从头开始往下遍历，无法像数组那样直接访问某个位置的元素。因为不知道链表的长度，所以也就不知道倒数第 n 个是哪一个位置。

我的想法： 既然不知道长度，那就先遍历一遍把所有节点收集起来，这样就能知道总长度了，然后再删除对应位置的节点。

具体步骤：

1. 定义一个数组，用来存储链表的每一个节点
2. 遍历链表，将每个节点存入数组
3. 计算要删除节点的索引位置：index = length - n
4. 特殊情况：如果 index === 0，说明删除的是头节点，直接返回数组中第二个节点作为新的头节点
5. 普通情况：将 index - 1 位置的节点的 next 指向 index + 1 位置的节点，完成删除
6. 返回数组的第一个节点作为新的头节点

代码实现

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  if (!head) return null;

  const nodes: ListNode[] = [];
  let current: ListNode | null = head;

  // 遍历链表，将节点存入数组
  while (current) {
    nodes.push(current);
    current = current.next;
  }

  const length = nodes.length;
  const indexToRemove = length - n;

  // 删除节点
  if (indexToRemove === 0) {
    // 删除头节点
    return nodes[1] || null;
  } else {
    // 删除非头节点
    nodes[indexToRemove - 1].next = indexToRemove + 1 < length ? nodes[indexToRemove + 1] : null;
  }

  return nodes[0];
}

优化思路

代码运行通过后，看到题目的进阶要求：你能尝试使用一趟扫描实现吗？

这让我想到了双指针的思路。

核心想法：

• 倒数第 n 个节点，其实就是正数第 length - n + 1 个节点
• 如果能让两个指针保持 n 步的距离，当右指针到达末尾时，左指针就正好在目标位置

具体做法：

1. 定义两个指针 left 和 right，都从头开始
2. 让 right 指针先走 n 步，这样 left 和 right 之间就相差 n 个位置
3. 然后让 left 和 right 一起前进，当 right 走到末尾时，left 就是要删除节点的前一个节点
4. 删除操作：left.next = left.next.next

为什么要用哑节点（dummy node）？ 如果直接从 head 开始，删除头节点时需要特殊处理。创建一个哑节点指向 head，这样就把所有情况统一了，最后返回 empty.next 即可。

优化后的代码

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  if (!head) return null;

  let empty = new ListNode(0, head);
  let left = empty;
  let right = empty;

  for (let i = 0; i < n; i++) {
    right = right.next;
  }

  while (right.next) {
    right = right.next;
    left = left.next;
  }

  left.next = left.next.next;

  return empty.next;
}

算法步骤（双指针法）

以 head = [1,2,3,4,5], n = 2 为例：

初始状态：
empty -> 1 -> 2 -> 3 -> 4 -> 5 -> null
↑
left, right

步骤1：right 先走 n=2 步
empty -> 1 -> 2 -> 3 -> 4 -> 5 -> null
↑             ↑
left         right

步骤2：同时前进，直到 right.next 为 null
empty -> 1 -> 2 -> 3 -> 4 -> 5 -> null
                  ↑             ↑
                left          right

步骤3：删除 left.next（节点4）
empty -> 1 -> 2 -> 3 -> 5 -> null
                  ↑
                left

返回：empty.next = [1,2,3,5]

关键点总结

1. 哑节点技巧：
   • 简化删除头节点的边界处理
   • 让所有删除操作统一为 prev.next = prev.next.next
2. 双指针间距：
   • 快指针领先慢指针 n 步
   • 快指针到末尾时，慢指针在倒数第 n+1 个位置
3. 边界条件：
   • 删除唯一节点：返回 null
   • 删除头节点：哑节点（empty）自动处理
4. 一次遍历的精髓：
   • 不需要提前知道链表长度
   • 通过固定间距的双指针巧妙定位目标位置