链式线性表倒数第K项这个题我前前后后见过不下十次——某公司笔试、某高校机试、课程设计里都出现过。说实话这题难度不大但特别能看出一个人写链表代码的基本功。最典型的两种做法我都实际写过先求长度再遍历以及双指针一次遍历。第二种写完之后就再也回不去了不管是代码量、边界处理还是面试官看你的眼神完全是两个档次。题目的描述很简单给定一个不带头节点的单链表要求返回倒数第K个节点的值。所谓“倒数第K”意思是从链表最后一个节点往前数第K个。读者最好先自己写一版再对着这篇文章看因为这题“能跑”和“跑得好”之间隔着不少细节。1. 题目拆解为什么“倒数第K项”总是被拿出来考1.1 题面到底在问什么先明确链表结构定义。在标准的C语言实现里链表节点一般长这样typedef struct ListNode { int val; struct ListNode *next; } ListNode;题目要求是在这个单链表上找到倒数第K个节点。比如链表是1 - 2 - 3 - 4 - 5K为2那答案应该是节点4。如果K为5答案是头节点1。这里有一个隐含前提必须想清楚单链表只能从前往后走不能回头。数组可以通过下标直接访问倒数第K个元素因为数组支持随机访问链表不行你访问第K个节点必须从头把前K个节点都走一遍。所以题目本质是在问在不额外开辟空间、不动链表结构的前提下如何用最少的遍历次数拿到从尾部数第K个节点。很多初学者第一反应是“先反转链表再数第K个”这种做法我极度不建议后面会专门说为什么。1.2 为什么不建议第二眼就想“先求长度再遍历”先求长度再遍历的思路本身没有错逻辑也非常直观第一遍从头到尾数出链表总长度N第二遍从头走N-K步就落在倒数第K个节点上。这个思路的复杂度是O(N)时间复杂度加O(1)空间复杂度理论上并不差。但问题在于第一它把一次本可以完成的查找拆成了两次遍历。虽然时间复杂度都是O(N)但常数时间翻倍。在链表特别长的情况下多一次完整的遍历就是实打实的性能损耗。第二代码表达力不够。你明明可以用一个指针在O(N)内完成却选择了两遍扫描面试官会怀疑你是不是不知道双指针的常见套路。第三“先求长度”这个思路有连带麻烦当你拿到长度N之后如果K比N大你得在第二遍遍历之前先判断“N - K是否合法”这个判断虽然简单但也多了一次逻辑分支。更关键的是如果这个函数在工程代码里被高频调用每次调用都要先完整遍历一遍链表再去查性能上会被人诟病。所以“先求长度再遍历”不是错误答案只是它是一个及格分答案。下面详细拆解这个答案能拿多少分以及它的真正短板在哪里。2. 第一种解法两趟扫描——能用但只算及格2.1 思路与代码实现先写一个最朴素的版本逻辑分三步从头遍历链表统计节点个数N。判断输入K是否合法K必须大于0且小于等于N。从头再遍历走N-K步到达的节点就是倒数第K个节点。ListNode* findKthFromEnd(ListNode* head, int K) { if (head NULL || K 0) { return NULL; } // 第一趟统计链表长度 int len 0; ListNode* p head; while (p ! NULL) { len; p p-next; } // 边界检查K不能大于链表长度 if (K len) { return NULL; } // 第二趟走 len - K 步 p head; for (int i 0; i len - K; i) { p p-next; } return p; }这个代码逻辑上没有问题几个边界也处理了链表为空返回NULLK非正返回NULLK大于长度返回NULL。2.2 这种写法真正的隐患我实测过很多遍这个版本在正确性上没什么可挑的。但有几个场景会让你觉得特别别扭场景一链表长度巨大。比如有几百万个节点K比较小比如K2。你为了拿倒数第二个节点第一趟硬是把整条链表从头到尾走了一遍。这意味着查询耗时和链表总长度强相关即便你要的只是尾部附近的数据。场景二函数被反复调用。在一个循环里反复调findKthFromEnd查不同K的倒数节点每次都要重新遍历整条链表。如果链表本身不变其实可以一次遍历就把结果缓存起来但两趟扫描的写法完全做不到这一点。场景三工程代码里链表是“只读且频繁查询”的。两趟扫描会把每次查询的代价放大到O(N)如果查询次数是M总代价是O(M*N)。而用双指针一次遍历单次查询仍然是O(N)但代码的常数更小配合缓存机制效果更好。这里“更好”不是玄学是实实在在的常数优化和代码可读性的提升。两趟扫描的另一个隐性问题是它不太好扩展。比如题目改成“删除倒数第K个节点”你两趟扫描确实也能做但双指针版本只需要在找到目标的同时保留前驱节点逻辑更顺手。我自己写工程代码时有个体会链表相关操作能一趟遍历完成的尽量不要两趟因为一趟遍历的代码通常更不容易在修改时引入bug。3. 第二种解法双指针一次遍历——面试官想看的版本3.1 核心思路把“倒数第K”翻译成“保持K步差”双指针的思路其实一句话就能说清楚先让第一个指针从头走K步第二个指针原地不动然后两个指针同时往前进当第一个指针走到链表末尾NULL时第二个指针正好指向倒数第K个节点。这里有一个很多人想不通的点为什么第二个指针停下来的时候位置恰好是答案用一个生活化的类比。假设你、我站在一条跑道的起点我先走K步然后停住你还在起点。接下来我每走一步你就走一步只要我始终比你快K步。当我走到跑道尽头的那一瞬间你距离跑道尽头正好是K步也就是说你的位置是从尽头往回数第K步的位置。链表里的“跑道尽头”就是NULL倒数第K个节点就是停下时第二个指针指向的节点。这里要特别注意一个细节第一个指针先走的是K步而不是K-1步。我见过很多代码把这里写错导致结果总差一个节点。原因很简单——倒数第1个节点就是最后一个节点你希望第二个指针指向最后一个节点时第一个指针应该已经越过了链表末尾到达NULL。如果第一个指针只走K-1步那当它走到链表最后一个节点时第二个指针指向的是倒数第K个节点的前一个节点答案就错了。有一种写法是让两个指针在链表尾部“对齐”而不是在NULL对齐那种写法里快指针先走K-1步但初学时很容易混淆。为了降低出错概率我这里统一用“走K步到达NULL”的描述这也是我认为最不容易写错的一个版本。3.2 完整代码与逐段注释ListNode* findKthFromEnd(ListNode* head, int K) { if (head NULL || K 0) { return NULL; } ListNode* fast head; // 快指针负责先走K步 ListNode* slow head; // 慢指针最终落在倒数第K个节点 // 第一步快指针先走K步 for (int i 0; i K; i) { if (fast NULL) { // K大于链表长度直接判定为非法输入 return NULL; } fast fast-next; } // 第二步两个指针同时前进直到快指针到达NULL while (fast ! NULL) { fast fast-next; slow slow-next; } return slow; }逐段解释关键逻辑第一段对head NULL和K 0的处理是防御性编程避免后面循环里对NULL解引用。第一段循环里if (fast NULL)的检查很关键。如果K比链表长度大比如链表只有3个节点你要倒数第5个节点那么快指针走到第4步时实际上已经指向NULL了此时整个链表根本没有倒数第5个节点直接返回NULL是正确行为。注意一个细节循环内先判断fast是否为空再执行fast fast-next。如果链表长度正好等于K比如3个节点K3那快指针在第4次循环判断时会发现fast NULL吗不会。第3次循环后fast指向NULL第4次循环进入时发现fast NULL此时return NULL的是K4的情况。K2时两次循环后fast指向第三个节点K3时三次循环后fast指向NULLK4时第四次循环进入时fast已经是NULL返回NULL。可以自己拿纸笔画一下这个流程画完就清楚了。第二步的while (fast ! NULL)循环每次让两个指针都前进一步。当fast走到NULL时slow恰好走了“链表长度 - K”步也就是从头部数这个位置的节点就是倒数第K个。这个版本的空间复杂度O(1)时间复杂度O(N)而且全程只遍历一次没有额外的长度统计代码量也比两趟扫描少了几行。更重要的是这个写法一旦理解之后遇到“找链表中间节点”“判断链表是否有环”这些题目思路可以无缝迁移。3.3 边界条件的处理细节双指针版本的边界条件比两趟扫描要多一些我到今天写这个代码依然会先在纸上过一遍边界列表边界一链表只有一个节点K1。快指针先走1步直接指向NULL慢指针不动返回head。正确。如果K2快指针进入第一次循环前判断fast NULL吗链表只有一个节点fast此时指向该节点不是NULL所以先走一步变成NULL第二次循环判断fast NULL成立返回NULL。K大于链表长度的场景被顺利拦截。边界二链表为空K任意。第一段if (head NULL)直接返回NULL不会进入后面的循环。边界三K0。题目通常不会让你找倒数第0个节点K 0直接返回NULL是最稳妥的做法。这个判断别图省事丢掉否则K0时会进入循环快指针没法走0步然后和慢指针同时前进最后返回的是最后一个节点逻辑完全错误。边界四K1。这是最容易测出问题的边界之一要求返回的是链表最后一个节点。按代码逻辑快指针先走1步到第二个节点如果有的话然后两个指针同步走快指针到NULL时慢指针正好在最后一个节点。我建议写完后专门用3个节点的链表测K1确认返回的节点值是3而不是2。边界五K等于链表长度。比如3个节点K3快指针走3步正好到NULL慢指针还在head返回头节点。这是倒数第K个节点的定义使然——倒数第3个节点就是头节点。这个边界在代码里不需要特判快指针走完K步后如果已经是NULL第二个循环一次都不执行slow保持head直接返回。边界条件想清楚之后双指针代码可以做到一次通过。但很多人在实际动手时仍然会出错原因往往出在“快指针先走K步”的循环里没有检查fast NULL或者把循环条件写成fast-next ! NULL。这些坑我下面专门用一个章节记录下来。4. 从“会做”到“做得爽”变式场景与工程化扩展4.1 常见变式删除倒数第K个节点会了查找删除倒数第K个节点就是顺水推舟的事。删除操作比查找多一个要求你必须拿到被删除节点的前驱节点否则无法让前驱的next指向被删节点的下一个节点。双指针版本删除倒数第K个节点思路是让慢指针最后落在目标节点的前驱而不是目标节点本身。做法是让快指针先走K步然后快慢指针同步走当快指针到达NULL时慢指针指向的是倒数第K个节点本身此时慢指针的next就是我们要删除的节点。但删除操作需要知道前驱所以我们可以让慢指针从head的前一个位置开始走或者更简单找到倒数第K1个节点然后删掉它的next。代码里我习惯用一个虚拟头节点来统一处理“删除头节点”的情况因为倒数第K个节点恰好是头节点时没有前驱节点逻辑会变得复杂ListNode* removeKthFromEnd(ListNode* head, int K) { // 引入虚拟头节点统一处理删除头节点的情况 ListNode dummy; dummy.next head; ListNode* fast dummy; ListNode* slow dummy; // 快指针先走K1步让slow最终落在目标节点的前驱 for (int i 0; i K; i) { if (fast NULL) { return head; // K非法不做删除 } fast fast-next; } while (fast ! NULL) { fast fast-next; slow slow-next; } // 删除slow后面的节点 ListNode* toDelete slow-next; slow-next toDelete-next; free(toDelete); return dummy.next; }这里的核心差异在于快指针先走了K1步而不是K步目的是让慢指针最终指向待删除节点的前驱。走了K1步的话快指针到NULL时慢指针落在倒数第K1个节点也就是倒数第K个节点的前驱。删除头节点的场景下虚拟头节点让代码完全不需要特判这个模式我强烈建议记住很多链表题目都能用虚拟头节点简化逻辑。4.2 K的合法性判断怎么设计才合理在工程代码里处理K的合法性远比在算法题里要考虑得多。算法题里的K通常给的是正整数且不大于链表长度但实际场景中调用者可能传入0、负数、超大值甚至浮点型如果接口没做类型约束的话。我推荐的处理策略是分两层接口层拦截函数入口直接判断K 0返回NULL或错误码不做任何链表遍历。遍历中检测快指针走K步的过程中每一步都检查fast是否为空。如果为空说明K超过链表实际长度立即返回NULL避免后面二次循环对NULL解引用。这两个检查缺一不可。只做第一层不做第二层K过大时会访问到NULL-next程序必然崩溃。只做第二层不做第一层K0时逻辑会错乱返回最后一个节点而不是空节点。我还见过一种写法是“先求长度再判断K是否合法”这种写法在双指针方案里反而多此一举。双指针方案在快指针走K步的过程中自然就能判断K是否合法前置长度统计完全是不必要的。这也是另一种角度证明双指针方案优于两趟扫描。4.3 双指针思路在其他数据结构里的迁移双指针这个思路不止能用在链表的倒数K项上。我实际在工程中用到的场景至少还有这几个场景A找链表的中间节点。快指针每次走两步慢指针每次走一步快指针到末尾时慢指针就在中间。这个思路和倒数K项本质一致都是一个“速度差”问题。场景B判断链表是否有环。快慢指针都从head出发快指针每次走两步慢指针每次走一步如果有环两者必然相遇。经典解法也是双指针只是执行方式不同。场景C有序数组/链表的合并去重。一个指针遍历另一个指针标记写入位置原地去重。本质是“读指针”和“写指针”的配合利用一个指针先行、另一个指针后续接力的思想。双指针之所以好用核心理由是它把“需要两趟才能确定答案”的问题压缩成“一趟同时维护两个视角”的问题。这在很多线性结构的处理里都会用到。我在做某跨平台系统的内存池管理时还用过类似思路在O(N)时间内定位空闲链表中的倒数第K个空闲块虽然场景完全不同但代码骨架几乎一样。所谓算法能力其实就是把这些常见思路练成肌肉记忆遇到新问题能快速迁移。5. 实际调试中遇到的坑与排查技巧5.1 典型报错与解决对照表我把实际写这个题目时最容易踩的坑整理成一个速查表每一行都是我或身边同学真实遇到过的情况。现象可能原因解决方案返回的节点是正确答案的前一个快指针走了K-1步而不是K步检查快指针定位循环的次数统一用K步K大于链表长度时程序崩溃快指针走到NULL后继续访问next在快指针步进前判断fast是否为NULLK1时返回空而不是最后一个节点边界判断顺序写错循环内多走了一步用3节点链表逐步调试打印fast和slow位置链表只有一个节点时K2返回错节点快指针步进前没有检查fast是否为空在for循环内先判断再步进在删除变式中删错了节点慢指针落在目标节点而非目标节点的前驱快指针先走K1步而不是K步头节点作为参数时的空指针问题没有用虚拟头节点统一逻辑删除场景引入dummy节点我印象最深的一次是在某次模拟机试中一个同学两趟扫描版本能过但改成双指针版本后K1一直返回倒数第二个节点。他调试了半小时最后发现是快指针定位循环里写了fast-next ! NULL作为循环条件导致快指针少走了一步。这种“差一步”的问题特别隐蔽因为链表短的时候结果并不总是错只有K取值在特定情况下才暴露出来。所以我现在写完双指针代码一定会用K1、KN、KN1三组用例轰炸一遍。5.2 我自己实测下来的几组测试用例给一段可以直接复制到本地跑的完整测试代码包含链表创建和几组关键用例方便读者拿到手就能验证自己写的函数#include stdio.h #include stdlib.h typedef struct ListNode { int val; struct ListNode *next; } ListNode; ListNode* createList(int arr[], int n) { if (n 0) { return NULL; } ListNode* head (ListNode*)malloc(sizeof(ListNode)); head-val arr[0]; head-next NULL; ListNode* tail head; for (int i 1; i n; 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 ! NULL) { printf(%d - , head-val); head head-next; } printf(NULL\n); } int main() { int arr[] {1, 2, 3, 4, 5}; ListNode* head createList(arr, 5); printList(head); // 用例1K1期望返回5 printf(K1: %d\n, findKthFromEnd(head, 1)-val); // 用例2K3期望返回3 printf(K3: %d\n, findKthFromEnd(head, 3)-val); // 用例3K5期望返回1 printf(K5: %d\n, findKthFromEnd(head, 5)-val); // 用例4K6期望返回NULL printf(K6: %s\n, findKthFromEnd(head, 6) NULL ? NULL(OK) : ERROR); // 用例5空链表期望返回NULL printf(empty: %s\n, findKthFromEnd(NULL, 1) NULL ? NULL(OK) : ERROR); return 0; }这段测试代码覆盖了K1、K长度一半、K等于长度、K大于长度、空链表五个场景。我把这五组用例存在编辑器里的代码片段中每次写完链表相关题目先跑一遍能排除掉80%的低级错误。5.3 几个写代码时可以抄的小习惯这个题目虽然小但它非常适合用来打磨写链表代码的习惯。我总结了几条自己长期在用的习惯第一所有链表函数入口先做防御性判断。不管题目有没有要求head NULL的判断都写上。这不仅是防止崩溃更重要的是让代码语义清晰读你代码的人第一眼就知道这个函数对空链表是什么行为。第二能用双指针就不要用两趟扫描。一次遍历能解决的问题拆成两次在工程代码里是会被review出来的。链表不支持随机访问一次遍历能拿到的信息尽量一次拿完。第三测试用例永远包含“边界非法”两组。我见过太多人在链表题上栽跟头是因为只测了正常情况。K1、K链表长度、K链表长度1、空链表、K0这五个用例跑完没问题基本可以上提交了。第四画图辅助思考。双指针这种代码别看它短逻辑绕起来真要命。我在白纸上画了不下十遍“快指针走K步、慢指针跟上”的过程图。画图不是为了现在的代码是为了建立空间直觉以后遇到更多指针配合的题目能快速反应。第五写注释的时候写“为什么”而不是“是什么”。比如“快指针先走K步而不是K-1步因为两个指针需要在NULL处对齐”这句话就比“快指针走K步”有用得多。半年后回来看代码能帮你省下大量回忆时间。我个人实际写这个题的经验是第一版用两趟扫描写了十分钟觉得别扭改成双指针又花了五分钟期间还写错过一次快指针走的步数。但自从把双指针思路吃透后面遇到“链表中倒数第K个节点”相关的所有变式包括删除、找中点、判环都是几分钟内一手写完直接过测试。这种“一套思路到处复用”的满足感只有真正动手写一遍才能体会到。上面说的这些坑和代码不用全背下来建议读者打开自己的编辑器把双指针版本敲一遍再用K1、KN、KN1这三组用例跑一遍。只要这三组对了这个题目就算真正拿下了。如果跑出来有问题对照着速查表逐项排查基本能定位到问题所在。
