京公网安备11010502063487号给定一个链表的头结点和整数 n，删除链表的倒数第 n 个结点，返回新的头结点。倒数第 n 个不能直接定位，最直接的想法是先数出链表长度 L，再走 L - n 步找到它的前一个结点。更常见的写法是快慢指针：让 fast 先走 n 步，然后 fast 和 slow 一起走，fast 走到最后一个结点时，slow 正好停在待删结点的前一个位置。本文验证两个常见说法：哑结点为什么必要，以及"一遍扫描"是否真的比"两遍扫描"移动得更少；给出五种语言的实现，并把快慢指针的移动做成分步演示。
完整题目见官方页面（链接在文末）。链表在测试里用整数数组表示，删除之后的结果也用数组表示。基准解直接在数组上切片删除，与指针操作是两种独立的写法。一共 10 组用例，覆盖：官方示例、只有一个结点、删除头结点、删除尾结点、结点值全相同、n 等于链表长度：
输入 [[1,2,3,4,5],2] 输出 [1,2,3,5] 输入 [[1],1] 输出 [] 输入 [[1,2],1] 输出 [1] 输入 [[1,2],2] 输出 [2] 输入 [[1,2,3],3] 输出 [2,3] 输入 [[1,2,3],1] 输出 [1,2]
快慢指针的写法里，slow 最终停在待删结点的前一个。但如果要删的恰好是头结点，它没有前一个结点。不加处理的话，fast 走完 n 步之后已经是空，后面读 fast.next 就会出错。哑结点（放在头结点之前的一个空结点）让头结点也有了前一个结点，就不用特判。下面是没有哑结点的写法与 solve 的真实结果：
# 没有哑结点的写法（fast、slow 都从 head 出发） [1, 2, 3, 4, 5], n=2: 无哑结点 -> [1, 2, 3, 5] solve -> [1, 2, 3, 5] [1, 2], n=1: 无哑结点 -> [1] solve -> [1] [1, 2], n=2: 无哑结点 -> AttributeError: 'NoneType' object has no attribute 'next' solve -> [2] [1], n=1: 无哑结点 -> AttributeError: 'NoneType' object has no attribute 'next' solve -> []
链表长度是 5、2 或 1，只要删除的不是头结点，两种写法都对；一旦 n 等于链表长度（删头结点），没有哑结点的写法就在 fast.next 上抛出了 AttributeError。所有五种语言的实现都用了哑结点。
先在头结点前放一个哑结点，fast、slow 都指向它。fast 先走 n 步，然后两个指针一起走，直到 fast 的下一个是空。这时 slow 的下一个就是待删结点，让 slow.next = slow.next.next 跳过它。返回哑结点的下一个。Python、Java、Go、JavaScript、C++ 都是真实编译运行的；C++ 里哑结点直接放在栈上，没有释放被删除的结点，因为这里的重点是指针逻辑，实际项目里需要释放。
Python · 解法代码class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def remove_nth_from_end(head, n): dummy = ListNode(0, head) # 哑结点：删除头结点时不用特判 fast = slow = dummy for _ in range(n): # fast 先走 n 步 fast = fast.next while fast.next: # 然后一起走，fast 到最后一个结点时，slow 正好在待删结点的前一个 fast = fast.next slow = slow.next slow.next = slow.next.next return dummy.next
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[1,2,3,4,5],2] → [1,2,3,5] [[1],1] → [] [[1,2],1] → [1] [[1,2],2] → [2] [[1,2,3],3] → [2,3] [[1,2,3],1] → [1,2]
Java · 解法代码class ListNode { int val; ListNode next; ListNode(int v) { val = v; } } class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0); // 哑结点：删除头结点时不用特判 dummy.next = head; ListNode fast = dummy, slow = dummy; for (int i = 0; i < n; i++) fast = fast.next; // fast 先走 n 步 while (fast.next != null) { // 然后一起走 fast = fast.next; slow = slow.next; } slow.next = slow.next.next; return dummy.next; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[1,2,3,4,5],2] → [1,2,3,5] [[1],1] → [] [[1,2],1] → [1] [[1,2],2] → [2] [[1,2,3],3] → [2,3] [[1,2,3],1] → [1,2]
Go · 解法代码type ListNode struct { Val int Next *ListNode } func removeNthFromEnd(head *ListNode, n int) *ListNode { dummy := &ListNode{Next: head} // 哑结点：删除头结点时不用特判 fast, slow := dummy, dummy for i := 0; i < n; i++ { // fast 先走 n 步 fast = fast.Next } for fast.Next != nil { // 然后一起走 fast = fast.Next slow = slow.Next } slow.Next = slow.Next.Next return dummy.Next }
$ go build -o bin . && ./bin < cases.jsonl [[1,2,3,4,5],2] → [1,2,3,5] [[1],1] → [] [[1,2],1] → [1] [[1,2],2] → [2] [[1,2,3],3] → [2,3] [[1,2,3],1] → [1,2]
JavaScript · 解法代码class ListNode { constructor(val = 0, next = null) { this.val = val; this.next = next; } } function removeNthFromEnd(head, n) { const dummy = new ListNode(0, head); // 哑结点：删除头结点时不用特判 let fast = dummy, slow = dummy; for (let i = 0; i < n; i++) fast = fast.next; // fast 先走 n 步 while (fast.next) { // 然后一起走 fast = fast.next; slow = slow.next; } slow.next = slow.next.next; return dummy.next; }
$ node run.js < cases.jsonl [[1,2,3,4,5],2] → [1,2,3,5] [[1],1] → [] [[1,2],1] → [1] [[1,2],2] → [2] [[1,2,3],3] → [2,3] [[1,2,3],1] → [1,2]
C++ · 解法代码struct ListNode { int val; ListNode* next; ListNode(int v) : val(v), next(nullptr) {} }; class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode dummy(0); // 哑结点：删除头结点时不用特判 dummy.next = head; ListNode *fast = &dummy, *slow = &dummy; for (int i = 0; i < n; i++) fast = fast->next; // fast 先走 n 步 while (fast->next) { // 然后一起走 fast = fast->next; slow = slow->next; } slow->next = slow->next->next; return dummy.next; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[1,2,3,4,5],2] → [1,2,3,5] [[1],1] → [] [[1,2],1] → [1] [[1,2],2] → [2] [[1,2,3],3] → [2,3] [[1,2,3],1] → [1,2]
共 10 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 10/10 Java 通过 10/10 Go 通过 10/10 JavaScript 通过 10/10 C++ 通过 10/10
这种解法常被说成"一遍扫描"，而先数长度再走 L - n 步是"两遍扫描"。我在 Python 里给两种写法都数了指针的移动次数（每次 next 计一次），链表长度 1000：
指针移动次数（每次 next 计一次），链表长度 L，删除倒数第 n 个： L=1000, n=1: 一遍扫描（快慢指针）1999 次 两遍扫描（先数长度再走 L-n 步）1999 次 L=1000, n=500: 一遍扫描（快慢指针）1500 次 两遍扫描（先数长度再走 L-n 步）1500 次 L=1000, n=1000: 一遍扫描（快慢指针）1000 次 两遍扫描（先数长度再走 L-n 步）1000 次
两种写法的移动次数完全一样。快慢指针只是把"数长度"和"走到位置"两件事交织在一起，总的指针移动次数是相同的，时间复杂度都是 O(L)。它的好处是只遍历一遍结构：数据从磁盘或网络流式到来、不能回头时更有用。这里我只数了指针移动，没有测量实际耗时和缓存行为，所以不能据此说两者的真实运行时间一样。
Python 版本另外和数组切片做了随机对拍：
随机对拍 5000 组（链表长度 1 到 12、结点值 0 到 20，n 取 1 到链表长度（覆盖删头结点、删尾结点）），solve 与 brute 的结果全部一致。
另外四种语言只在上面 10 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方示例 [1, 2, 3, 4, 5]，删除倒数第 2 个。第一个结点是哑结点。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示最终得到的链表与 solve 的返回值一致。fast（蓝色）先走 2 步，之后两个指针同步走，直到 fast 在最后一个结点。