链表专题(四)：一把尺子的智慧——「删除链表的倒数第 N 个结点」

场景想象：

你手里有一根链表，但你不知道它有多长（不能直接得到 length）。

任务是：找到倒数第 N 个节点，把它删掉。

• 如果是数组，我们可以直接算下标length - N。

• 但链表是单向的，我们不知道终点在哪。

• 笨办法：先跑一趟量长度L，再跑一趟去L - N的位置。虽然是 $O(N)$，但遍历了两次。

• 聪明办法（快慢指针）：

  想象你手里有一把长度为 N 的“尺子”（或者一根棍子）。

  1. 让快指针先跑N步（撑开尺子）。

  2. 然后让快指针和慢指针同时往后移。

  3. 当快指针碰到链表尽头（null）时，慢指针（尺子的另一头）正好就停在了倒数第 N 个节点的位置！

核心痛点：

要删除一个节点，我们需要找到它的前一个节点 (Pre)。

所以，我们的“尺子”实际上要稍微再长一点，或者让快指针多走一步，这样慢指针才能停在目标节点的前一位。

力扣 19. 删除链表的倒数第 N 个结点

https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

题目分析：

• 输入：链表头head，整数n。

• 目标：删除倒数第n个节点。

• 输出：新头节点。

例子：1 -> 2 -> 3 -> 4 -> 5,n = 2

• 倒数第 2 个是4。

• 删除后：1 -> 2 -> 3 -> 5。

核心思维：虚拟头结点 + 快慢指针 (Gap法)

1. 虚拟头结点 (Dummy)：

   • 为什么又要它？因为如果要删的是倒数最后一个（也就是正数第一个，头结点），没有 Dummy 会很麻烦。

2. 快指针先跑n + 1步：

   • 为什么是n + 1？

   • 因为我们希望当快指针指向null（越界）时，慢指针正好停在倒数第 n 个节点的前一个。

   • 这样我们才能执行slow.next = slow.next.next。

代码实现 (JavaScript)

JavaScript

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @param {number} n * @return {ListNode} */ var removeNthFromEnd = function(head, n) { // 1. 虚拟头结点：防止删除的是头结点（比如 list=[1], n=1） const dummy = new ListNode(0, head); // 2. 定义快慢指针，初始都指向 dummy let slow = dummy; let fast = dummy; // 3. 让快指针先走 n + 1 步 // 目的：拉开 n+1 的间距。这样当 fast 走到 null 时，slow 正好在目标的前一位 for (let i = 0; i <= n; i++) { fast = fast.next; } // 4. 双指针同时移动 // 只要 fast 还没掉出悬崖（null），就一起往后挪 while (fast !== null) { slow = slow.next; fast = fast.next; } // 5. 此时 slow 指向的是“倒数第 n 个节点”的【前驱节点】 // 执行删除操作 slow.next = slow.next.next; return dummy.next; };

深度模拟

假设list = [1, 2, 3, 4, 5],n = 2(删除 4)。

• 初始：dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null

• Fast 先跑 3 步 (n+1)：

  • 0步: dummy

  • 1步: 1

  • 2步: 2

  • 3步: 3

  • 此时fast在 3，slow在 dummy。

• 一起跑：

  • Round 1:fast->4,slow->1

  • Round 2:fast->5,slow->2

  • Round 3:fast->null,slow->3

• 停！fast是 null 了。

• 操作：slow现在指着 3。

  • slow.next是 4 (目标)。

  • slow.next = slow.next.next(也就是 5)。

  • 链表变成1 -> 2 -> 3 -> 5。完美！

总结

这道题是**“固定间距双指针”**的教科书级应用。

• 关键点：只要看到“倒数第 K 个”，马上反应过来 ->让快指针先走 K 步。

• 细节：为了方便删除，我们通常让快指针多走一步（或者判断条件改为fast.next !== null），目的是拿到前驱节点。

下一题预告：相交链表

刚才我们用两个指针一前一后跑。

下一题 LC 160. 相交链表（专题五），我们要让两个指针在两条不同的路上跑。

• 题目：给你两个链表 A 和 B，它们在某个节点汇合了（变成 Y 字形）。请你找到这个交点。

• 难点：A 和 B 长度不一样，直接遍历会错开，怎么让它们在终点相遇？

• 技巧：“走过你走的路”—— 极其浪漫的解法。

准备好继续了吗？