我在面试候选人的时候经常用一道题来摸底——删除链表的倒数第 n 个节点。这道题在 LeetCode 上是第 19 题几乎所有主流刷题平台都收录了它。表面看非常基础链表结构、一次遍历、双指针都是老生常谈。但真放到白板上写能一次写对的人少得可怜。你问他思路他说快慢指针快指针先走 n 步你让他写代码他会漏掉删除头节点的分支或者忘记处理 n 等于链表长度的边界。这篇文章不打算只给一个答案。我想把这个问题从原理到坑位完整拆开讲为什么倒数会让一个简单的删除操作变难双指针为什么能一次遍历解决问题边界条件里藏着哪些高频失分点以及在实际工程链表操作里被无数人踩过的教训。无论你是刚开始学数据结构的学生还是刷题准备面试的开发者或者是工作中需要手写链表的从业者这篇内容应该都能给你提供点不一样的东西。1. 倒数这两个字为什么能把简单删除变难1.1 题目本身并不复杂先明确题面。给定一个单链表的头节点 head删除从链表末尾数起的第 n 个节点并返回链表的头节点。比如链表是 1 - 2 - 3 - 4 - 5n 2删除倒数第 2 个节点 4最终得到 1 - 2 - 3 - 5。删除一个链表节点最朴素的操作是找到它的前驱节点然后把前驱的 next 指针指向被删节点的后继。这句话用代码表达是prev-next target-next。问题在于单链表的节点只有指向后继的 next 指针没有指向前驱的 prev 指针。你想删除哪个节点必须先拿到它的前一个节点。而倒数第 n 个节点到底在哪直接拿肉眼是看不见的。1.2 单链表天生只能向前看这里有个直觉上的错位。我们人脑中的倒数概念是空间性的一列人从队尾往前数第 n 个你能直接看到队尾是谁。但单链表的内存模型不是这样就算你记住了最后一个节点也无法从它跳回前一个节点——每个节点只保存 next 的地址尾节点的 next 是 NULL。要从头访问到尾只能一个指针顺着 next 一路往后走没有任何捷径。我经常用一个排队类比向新人解释假设你只能拉着前面人的衣角往前走想找到队伍里倒数第 3 个人你不能回头数只能从队头开始一个一个数过去。除非事先知道队伍总长否则你根本不知道走到哪里该停。这个只能向前走的约束就是整道题的核心矛盾。1.3 朴素解法先数长度再走一遍既然核心矛盾是不知道链表多长那最简单的解法自然就是先遍历一次数出长度 L然后知道倒数第 n 个节点其实是从头数第 L - n 1 个节点。删除它需要走到它前一个位置也就是从头开始走 L - n 步。int getLength(struct ListNode* head) { int len 0; while (head) { len; head head-next; } return len; } struct ListNode* removeNthFromEnd(struct ListNode* head, int n) { int len getLength(head); struct ListNode dummy; dummy.next head; struct ListNode* cur dummy; for (int i 0; i len - n; i) { cur cur-next; } struct ListNode* target cur-next; cur-next target-next; free(target); return dummy.next; }这段代码是能跑通的时间复杂度 O(L)空间复杂度 O(1)。但它有两个问题。第一遍历了两次。第一次数长度第二次找位置总共走了约 2L 步。对性能敏感的场景来说这不是最优雅的。第二面试官的心理预期不是这个。当题目提到倒数时出题人的潜台词是希望你不依赖长度也能定位节点。刷题圈子里说一次遍历解法指的就是双指针法。如果你在面试时给出两次遍历的版本运气好对方点点头运气不好他会追问一句能不能只遍历一遍2. 双指针法完整推演一次遍历不是魔法是位置差管理2.1 核心思路让两个指针之间保持 n 个身位的距离双指针法有个非常直观的物理类比。想象两个人在跑道上同向跑步一个人速度快先跑出去另一个人晚点再出发。如果先出发的人刚好领先 n 步那么当领先者到达终点线时后出发的人距离终点正好还有 n 步——他站的那个位置就是从终点往回数的第 n 个位置。放到链表里终点就是尾节点的 next也就是 NULL。具体怎么操作呢先用快指针 fast 从头出发先向前走 n 步。此时 fast 和 slow 之间的距离恰好是 n 个节点。然后 fast 和 slow 同步向后移动每次都走一步。当 fast 到达链表最后一个节点时fast-next 为 NULL这时 slow 停在哪根据距离关系slow 应该停在倒数第 n1 个节点的位置也就是待删节点的前一个节点。为什么要让 fast 走到尾节点而不是走到 NULL因为我们要的是待删节点的前驱。如果 fast 走到 NULLslow 恰好落在待删节点上那还得再想办法找它的前驱反而绕了。让 fast 停在尾节点slow 自然站在前驱位置直接执行删除就行。2.2 手把手模拟一遍拿 1 - 2 - 3 - 4 - 5 这个链表举例n 2目标是删除节点 4。初始状态slow 和 fast 都指向虚拟头节点 dummydummy.next 1。第一步fast 先走 2 步到达节点 2。此时 fast 领先 slow 两个节点。然后 while 循环条件是 fast-next 不为空fast 从 2 走到 3slow 从 dummy 走到 1fast 从 3 走到 4slow 从 1 走到 2fast 从 4 走到 5slow 从 2 走到 3。现在 fast 指向节点 5fast-next 是 NULL循环停止。slow 指向节点 3正好是节点 4 的前驱。执行 slow-next slow-next-next就把节点 4 摘下来了。这个例子里fast 总共走了 4 步从 dummy 到节点 5slow 走了 3 步从 dummy 到节点 3。相比先数长度再删除的两次遍历总步数大约少了一次完整的链表遍历。2.3 dummy 节点为什么要站在链表前面垫一步上面的模拟里我引入了 dummy 虚拟头节点。这是链表题里一个很小但极其实用的技巧。假设不使用 dummy直接让 slow 和 fast 指向 head。如果 n 恰好等于链表长度比如链表有 5 个节点n 5要求删除头节点。按照双指针逻辑fast 先走 5 步会走向 NULL。此时 slow 还停在 head循环无法继续。为了删除头节点你得单独写一个判断if (slow head) { head head-next; }之类的分支。这种特殊分支写起来没有问题但很容易出错——很多人写着写着就忘记处理这个情况导致 n 等于链表长度的用例直接崩掉或返回错误结果。dummy 的思路是在真正的头节点前面人为加一个虚拟节点它的 next 指向 head。这样头节点的前驱就不再是不存在的东西而是 dummy。不管删除哪一个节点删除逻辑都统一成把某个节点的 next 指向它的下下个节点不需要为头节点写特例。最后函数返回 dummy.next本质上就是返回可能被删除后的新头。这里提醒一个 C 语言的细节dummy 节点可以用栈上的局部变量声明比如struct ListNode dummy; dummy.next head;。只要在整个函数执行期间它不会被提前释放就是安全的。也可以用 malloc 动态分配但别忘了在函数结束前 free 掉否则泄漏内存。我见过不少人在考试里真的 malloc 一个 dummyreturn 之前又忘记 free被内存检测工具报错。2.4 完整 C 语言实现struct ListNode* removeNthFromEnd(struct ListNode* head, int n) { if (head NULL || n 0) { return head; } struct ListNode dummy; dummy.next head; dummy.val 0; // 这个字段用不到但有些编译器会检查未初始化 struct ListNode *fast dummy; struct ListNode *slow dummy; // fast 先走 n 步 for (int i 0; i n; i) { if (fast-next NULL) { // 链表长度小于 n无法删除直接返回原链表 return head; } fast fast-next; } // fast 和 slow 同步前进直到 fast 到达最后一个节点 while (fast-next ! NULL) { fast fast-next; slow slow-next; } // 此时 slow 指向待删节点的前驱 struct ListNode *toDelete slow-next; slow-next toDelete-next; free(toDelete); return dummy.next; }这个版本有两个关键点。首先在 fast 先走 n 步的循环里我加了fast-next NULL的检查用来防御 n 大于链表长度的非法输入。其次fast 先走的步数是 n 而不是 n1配合while (fast-next ! NULL)这个循环条件能让 slow 停在正确的前驱位置。这两处如果写错结果差之毫厘谬以千里。3. 边界条件逐个击破多数提交都挂在看起来合法的用例上这道题在面试中真正的失分点往往不是主体逻辑而是边角条件的处理。LeetCode 的判题器非常严格什么空链表、单节点链表、n 等于链表长度全部都要能跑通。下面我们把每种情况过一遍。3.1 链表中只有一个节点链表只有一个节点 5n 1。要求删除倒数第 1 个节点也就是删除它自己最终链表应该为空。用我们的函数走一遍dummy.next 5fast 从 dummy 走 1 步到达节点 5while 循环判断 fast-next NULL不进入循环。slow 还停在 dummy。执行删除toDelete slow-next也就是节点 5slow-next toDelete-next也就是 NULLfree 掉节点 5。返回 dummy.next即 NULL。结果正确。如果不小心在 fast 先走的循环里用了fast NULL而不是fast-next NULL作为越界条件在处理单节点链表时 fast 走 1 步正好到节点 5不会变成 NULL但接下来 while 循环条件判断 fast-next 时就要小心。这个细节很考验对边界感觉的敏锐程度。3.2 n 等于链表长度删除头节点链表 1 - 2 - 3 - 4 - 5n 5。要求删除倒数第 5 个节点也就是头节点 1。fast 从 dummy 走 5 步dummy - 1 - 2 - 3 - 4 - 5最后 fast 停在节点 5。while (fast-next ! NULL) 判断 5 的 next 是 NULL不进入循环。slow 还是 dummy。删除 slow-next也就是节点 1返回 dummy.next 即节点 2。整个链表变成 2 - 3 - 4 - 5。正确。这就是 dummy 节点最核心的价值它把删除头节点这个看起来特殊的操作吸收进了统一的删除逻辑里。如果你不用 dummy这一步就必须为 slow head 的情况单独写分支多写一行代码就多一处写错的可能性。3.3 空链表和非法参数防御性代码是职业习惯题目通常保证 n 是合法的正整数且链表非空。但写工程代码的人都会习惯性做防御。我在函数开头就写了if (head NULL || n 0) return head;。这两行可以避免在最糟的情况下出现段错误或无限循环。n 大于链表长度的情况也要考虑。比如链表只有 3 个节点n 5n 比总长度还大这时候倒数第 5 个节点根本不存在。我们的实现里fast 先走 n 步时会在fast-next NULL处停下来并返回原链表不会出现指针越界。有人可能觉得这些判断是多余的。但实际工程中链表操作一旦越界就会产生难以定位的内存错误可能在几毫秒后程序才崩溃排查成本高得吓人。多写两行防御代码是对自己也对调用方负责。3.4 不同语言里的隐藏地雷同样的逻辑换一种语言就会换一种坑。C 语言要求手动管理内存。删除节点后要 free但 free 前必须先把后继指针保存好否则节点被释放后它的 next 就变成悬空指针。上面的实现里写的是slow-next toDelete-next; free(toDelete);先改指针再释放顺序反了就会出问题。Python 和 Java 没有手动释放的概念删除节点就是调整引用。但 Python 里有个问题如果你用一个局部变量to_delete slow.next然后slow.next to_delete.next对 GC 来说原节点失去引用后被回收一切正常。麻烦的是如果你在函数外部还持有原节点的引用它并不会消失只是从链表里摘出去了这点和 C 语言的删除语义不同。C 里用 new 创建的节点要 delete用智能指针 std::shared_ptr 指向节点时调整 next 引用就可能触发链式析构小心别把后面一串节点都给释放掉。说白了不同语言在表达删除时语义差别很大面试时如果对方允许你自由选择语言选你最熟、最能控制内存的。3.5 一份可以直接抄的测试用例清单我整理自己的刷题笔记时会把边界用例单独记下来每次写完函数先拿这套用例过一遍比盲目提交快得多用例输入链表n期望输出正常用例[1,2,3,4,5]2[1,2,3,5]删除头节点[1,2,3,4,5]5[2,3,4,5]单一节点[1]1[]两个节点删第一个[1,2]2[2]两个节点删第二个[1,2]1[1]空链表[]1[]n 大于长度[1,2,3]5[1,2,3]这套用例覆盖了正常逻辑和所有我能想到的边界跑通他们之后提交时心里就踏实多了。4. 解法对比不是所有场景都该用双指针双指针是这道题的优解但不是唯一解。实际面试和工程中你可能会遇到需要换思路的情况。这节我们把几种常见解法放在一起对比。4.1 递归解法用调用栈从后往前数递归的魅力在于它天然具备回溯的能力。当递归进入最深一层触底返回时每一层都可以携带一个当前是倒数第几的信息。思路是先递归到链表末尾回溯过程中计数。回到某个节点时如果它是倒数第 n1 个节点就把它的 next 指向 next-next。代码可以写成class ListNode: def __init__(self, val0, nextNone): self.val val self.next next class Solution: def removeNthFromEnd(self, head, n): def dfs(node): if node.next is None: return 1 # 当前节点是倒数第 1 个 cur dfs(node.next) 1 # 当前节点是倒数第 cur 个 if cur n 1: node.next node.next.next return cur dummy ListNode(0, head) dfs(dummy) return dummy.next这个写法很巧妙但它的空间复杂度是 O(L)因为递归的每一层调用都占据栈空间。当链表长度达到几百万甚至上千万时递归深度可能超过栈限制直接栈溢出。所以在生产环境里我通常不会用递归处理超长链表的删除操作。4.2 栈解法空间换清晰度另一种从后往前的思路是借助栈。遍历整个链表把每个节点指针压入栈中。由于栈是后进先出弹栈访问节点的顺序就是从尾到头。弹栈 n 次后栈顶元素就是待删节点但删除它需要拿它的前驱——看看栈顶的下一个元素就行。这种解法逻辑简单但同样需要 O(L) 的额外空间而且要做一轮完整的压栈。栈解法在处理倒数第 n 个这类问题上代码容易看懂但性能上和双指针比没有任何优势。笔试时如果没时间想双指针写栈解法也能得分但面试官大概率会追问能不能优化空间这时候就要回到双指针。4.3 复杂度对比解法时间复杂度空间复杂度遍历次数适用场景先数长度O(L)O(1)约 2 次思路直白适合初学理解双指针O(L)O(1)约 1 次面试标准答案性能最佳递归O(L)O(L)1 次代码简洁但链表长时可能栈溢出栈O(L)O(L)1 次理解直观适合快速实现双指针的时间复杂度和其他几种一样都是 O(L)但省掉了额外空间并且遍历次数也更少。如果严格说一次遍历完成操作双指针是唯一符合要求的解。它的本质不是魔法而是把差值变成了两个指针位置之间的距离差用距离去替代对链表长度的依赖。4.4 顺着这道题延伸出去的变体双指针的思路一旦掌握可以复用在一大批链表题上。比如查找链表的中间节点用快慢指针快指针每次走两步慢指针每次走一步快指针到达末尾时慢指针正好停在中点。再比如判断链表是否有环快慢指针在环内必定相遇。这些题的核心都是利用两个指针的不同步长制造位置差和本节的题同源。再想深一层如果链表换成双向链表删除倒数第 n 个节点反而更简单——先走到尾节点再沿着 prev 指针往回走 n-1 步直接拿到待删节点本身及其前驱。但现实工程里双向链表的实现更麻烦维护成本也更高。理解不同数据结构对同一操作的友好程度差异对选型很有帮助。5. 从算法题到工程实践链表删除操作里的真实教训刷题归刷题真到写工程代码的时候链表操作就没那么干净了。我在实际项目里维护过内存链、任务队列、LRU 缓存见过不少因链表删除导致的诡异问题这节专门讲讲教训。5.1 先保存后继再动指针别让自己丢了后路链表删除最常见的 bug是在释放内存之前就把 next 指针覆盖了。比如这样写free(cur-next); // 先把后继节点释放了 cur-next cur-next-next; // 访问已被释放的内存行为未定义这属于典型的悬空指针错误。正确的顺序永远是先用一个临时变量保存待删节点的 next再修改前驱的 next 指针最后释放。即struct ListNode *nextNode toDelete-next; cur-next nextNode; free(toDelete);。顺序一旦颠倒轻则逻辑错误重则立刻段错误。别问我怎么知道的。5.2 删除节点不等于释放内存有些语言自动管理内存删除链表节点时不需要也不能手动 free。但 C/C 里从链表摘除和释放内存是两件事。你完全可以把节点从链表里摘出来但暂时不释放它留着做复用。很多内存池的做法就是空闲链表里的节点只是被摘下来了并没有被 destroy等下次分配时直接把节点重新挂回去。理解这层区别才算真正理解了链表的存储管理。5.3 头节点变化了调用方还拿着旧头吗删除操作如果发生在头节点新的链表头就变了。C 语言里通过返回值传递新头是最常见做法像我们上面实现的return dummy.next。但如果函数签名设计成void removeNthFromEnd(struct ListNode **head, int n)那就得用二级指针修改调用方的头指针。很多工程代码里的链表 bug 都出在这个细节函数内部改了头外层却还在用旧头导致整个链表越走越偏。5.4 一个完整可复现的测试程序光说不练假把式我把前面所有思路整合成一个可以直接编译运行的 C 程序。你把它复制到本地跑一遍能更直观地看到双指针删除的整个过程#include stdio.h #include stdlib.h typedef struct ListNode { int val; struct ListNode *next; } ListNode; ListNode* createList(int arr[], int len) { if (len 0) return NULL; ListNode *head (ListNode*)malloc(sizeof(ListNode)); head-val arr[0]; head-next NULL; ListNode *tail head; for (int i 1; i len; i) { ListNode *node (ListNode*)malloc(sizeof(ListNode)); node-val arr[i]; node-next NULL; tail-next node; tail node; } return head; } void printList(ListNode *head) { while (head) { printf(%d - , head-val); head head-next; } printf(NULL\n); } void freeList(ListNode *head) { while (head) { ListNode *tmp head; head head-next; free(tmp); } } ListNode* removeNthFromEnd(ListNode *head, int n) { if (head NULL || n 0) { return head; } ListNode dummy; dummy.next head; ListNode *fast dummy; ListNode *slow dummy; for (int i 0; i n; i) { if (fast-next NULL) { return head; } fast fast-next; } while (fast-next ! NULL) { fast fast-next; slow slow-next; } ListNode *toDelete slow-next; slow-next toDelete-next; free(toDelete); return dummy.next; } int main() { int arr[] {1, 2, 3, 4, 5}; ListNode *head createList(arr, 5); printf(原始链表: ); printList(head); head removeNthFromEnd(head, 2); printf(删除倒数第2个节点: ); printList(head); head removeNthFromEnd(head, 4); printf(再删除倒数第4个节点: ); printList(head); freeList(head); return 0; }这段程序在本地跑一下输出应该是原始链表: 1 - 2 - 3 - 4 - 5 - NULL 删除倒数第2个节点: 1 - 2 - 3 - 5 - NULL 再删除倒数第4个节点: 2 - 3 - 5 - NULL第一次删除节点 4第二次链表长度为 4倒数第 4 个节点是头节点 1删除后头变成 2。5.5 真实联想LRU 缓存中的删除最久未使用节点算法题刷多了之后你会发现链表的删除操作在真实项目里无处不在。最典型的是 LRU 缓存。设计一个 LRU 缓存时通常用哈希表加双向链表哈希表负责快速查找双向链表负责维护访问顺序。缓存满了之后要淘汰最久未使用的节点——具体操作就是把双向链表的尾节点摘下来再更新哈希表。这个场景和我们的题目有个共同的关键点删除一个节点之前你必须持有它的前驱或是在双向链表里持有它自身的指针。分布式缓存中间件、操作系统页面置换、数据库的缓冲池管理底层都有类似的链表操作。刷题时练出的那种对前驱和后继指针的敏感度在做这些系统设计时特别派得上用场。另外真实项目里的链表往往不是单独存在的它和哈希表、数组、堆等结构组合在一起。删除链表节点时你可能还得同步更新其他索引结构否则就会出现链表里删掉了索引里还留着的数据不一致问题。这也是为什么很多经验丰富的工程师写链表操作时总会先画出完整的结构图标清楚所有需要同步修改的引用再动手写代码。就我个人经验来说这道题是检验链表基本功的试金石。它不要求你懂什么高深算法但考察的是对单链表结构、指针操作、边界条件、空间复杂度这四件事的综合理解。如果你能把双指针的原理讲清楚把 dummy 节点的作用说透再把上面所有边界用例都处理妥当那么绝大多数面试官都会认为你链表功底过关。面试之外这套思维方式对阅读复杂工程代码也很有帮助——读别人的链表操作时你就知道该留意哪几个容易埋雷的位置。
