如果你手头有2009年的408真题翻到数据结构部分最后那道算法大题大概率会看到一个熟悉得不能再熟悉的面孔带头结点单链表查找倒数第k个结点的位置。我第一次做这道题的时候心里想的是这还不简单先数一遍链表有几个结点再正着走到第n-k1个不就行了。结果一对参考答案就发现出题人在题干里写的“尽可能高效”五个字才是这道题真正的考点所在。2009年是408统考的第一年这道算法题基本奠定了后来十几年408算法大题的出题风格不考偏题怪题考的就是基础数据结构的边界意识和算法设计能力。对准备考研408的同学来说这题是绕不开的入门题对只刷LeetCode Hot100、或者在准备华为OD机试的同学来说这也是双指针思想在链表上最朴素也最典型的一次应用。这篇文章我就把这题从审题、推演、写码到判卷全部掰开揉碎讲一遍看完你不仅能拿下这道题还能顺便把链表双指针这一类题都吃透。1. 题目到底问什么2009年408链表题的精确描述与三个隐藏考点先花30秒把当年的题目完整看一遍很多同学做题做错不是因为代码能力不行而是题干都没读透。已知一个带头结点的单链表结点结构为(data, link)该链表只给出了头指针list。在不改变链表的前提下请设计一个尽可能高效的算法查找链表中倒数第kk为正整数个位置上的结点。若查找成功算法输出该结点的data域的值并返回1否则只返回0。要求描述算法的基本设计思想。根据设计思想采用C或C或Java语言描述算法关键之处给出注释。说明算法的时间复杂度和空间复杂度。这道题属于408数据结构部分的大题分值大概在8到10分之间设计思想、代码实现、复杂度分析三个维度都有对应的给分点。第一次做这题的人很容易犯一个相同的错误上来就写代码忽略了题目里的“尽可能高效”。1.1 这三个隐藏考点是拿满分的分水岭第一个隐藏考点是“带头结点”。带头结点意味着链表的第一个有效数据结点是list-link而不是list本身。很多参考答案和经典教材里指针的初始化都是从list-link开始的你要是从list开始移动最后输出的data值就是头结点里那段未初始化的垃圾数据整个结果完全不可控。第二个隐藏考点是“不改变链表”。这句话可以直接理解为你不能把链表倒置不能交换结点位置连改指针方向都不行。我见过有同学想“先把链表反转再查第k个”这种思路在时间复杂度上可能勉强过得去但直接违反了题干约束就算代码写出来也不得分。第三个隐藏考点是“尽可能高效”。这里的高效主要指的是时间复杂度。单链表只能从前往后遍历如果你先用一趟扫描求出链表长度n再从头走n-k步找到目标结点这个算法的时间复杂度严格说是O(n)但它扫描了两次链表。在408的语境里更优的解法应该是一趟扫描完成也就是双指针法。后面我会具体证明为什么双指针是这道题的标准答案。1.2 为什么这道题能成为408的“压舱石”题目2009年这道题之后408的数据结构算法大题几乎每年都保持类似的命题思路要么考链表要么考二叉树偶尔考数组和栈队列但核心永远是“用最朴素的算法操作最基础的数据结构并给出严格的时间和空间复杂度分析”。这道题之所以被各大考研机构收录为经典是因为它精准踩中了三个常考能力一是对单链表逻辑结构的理解二是对双指针这种优化手段的灵活运用三是对边界条件的防御性思考。可以说把这一题吃透考研408数据结构部分最大的那道题你就有了一个基本盘。2. 从“数长度再走一遍”到双指针两种解法的完整推演在讲标准答案之前我先把大部分人的第一反应展开讲透因为这也是评分标准里非常重要的参照系。只有知道常规解法输在哪里你才能理解双指针解法赢在哪里。2.1 常规解法两次遍历思路简单但不够“高效”假设链表有n个结点。第一次遍历从头走到尾数出n是多少。目标结点是倒数第k个也就是正数第n-k1个。第二次遍历从头开始走每走一步计数加1走到第n-k1个结点就是答案。这个思路本身没有任何错误甚至在k非常接近1或n的时候代码写起来比双指针还要直观。但它的问题在于链表是单向的第二次遍历必须从头开始走如果链表很长比如有100万个结点你要先完整走一遍数长度再从头走一遍找位置总共移动约100万加100万减k次指针。对于“只查一次”的场景来说这其实也能接受但题目明确要求“尽可能高效”所以这个解法只能算合格不能算优秀。从考场的角度说如果实在想不出双指针写这个解法也能拿到一定的分尤其是设计思想表达清楚、代码无语法错误的话通常能拿到基础分。但你要是想冲击满分必须学会双指针。2.2 双指针解法让两个指针保持k-1的间距双指针的思路并不复杂用一个场景类比你就明白了。想象你和一个朋友在一条单行道上走你让他先走k步然后停下来等你等你跟上他之后你们俩保持同步往前走。当他走到路的尽头不能再走时你所站的位置就是从后往前数的第k个位置。对应到链表上就是设两个指针p和q初始都指向链表的首元结点也就是list-link。q先移动同时用一个计数器count记录q已经走过的步数。当count小于k的时候只有q移动p不动一旦count不小于k也就是q已经领先了k步之后q每移动一步p也跟着移动一步。这样当q走到了链表末尾的NULL时p正好指向倒数第k个结点。这个算法的精妙之处在于两个指针虽然是都从头走到尾但它们是在同一趟遍历中完成的。q走完整个链表需要n步p在q走了k步之后才开始走总共走了n-k步两个指针的移动总数是n加n-k也就是2n-k时间复杂度仍然是O(n)但整个过程只有一趟扫描。这就是“尽可能高效”的题眼所在。2.3 一个具体例子的完整走位过程为了把双指针的原理彻底讲清楚我手动模拟一个例子。假设链表有10个结点结点的data值依次是1、2、3、4、5、6、7、8、9、10我们要找倒数第3个结点正确答案应该是数据的8的那个结点因为它正数第8个倒数第3个。n10k3一开始p和q都指向data1的结点count0。q开始移动q的步数count的值p的位置第1步count变为1还在data1第2步count变为2还在data1第3步count变为3还在data1第4步count3q继续走data2第5步count3q继续走data3第6步count3q继续走data4第7步count3q继续走data5第8步count3q继续走data6第9步count3q继续走data7第10步count3q继续走data8当q走到第10步时q指向data9的结点。q再移动一步就到NULLp继续走到data8的结点。此时qNULL循环结束p指向data8的结点正好是倒数第3个。整个走位过程一目了然这个表也是你在答题时可以写在草稿纸上帮助自己理清逻辑的。2.4 边界条件为什么这道题的坑全在边界上双指针的代码框架不难难的是把边界条件处理完整。我按照408阅卷的常见标准把边界情况一个个列出来k1指的是最后一个结点。按照上面的走位q到头时p正好指向最后一个结点正确。kn指的是第一个结点。q从首元结点走n步到NULLp在count等于n之前一直不动直到倒数第n步才刚起步最后q到NULL时p还在首元结点正确。kn也就是k比链表长度还大。此时q已经走完了整个链表到NULLcount始终小于k循环结束后通过if(countk)返回0正确。空链表也就是只有头结点。p和q都指向NULLwhile循环一次都不执行count0k是正整数countk成立返回0正确。k0题目已经说明k是正整数所以原始答案里一般不处理这种情况。但如果你在写工程代码应该在函数开头加一个if(k0) return 0防止k0时出现p-data访问空指针的问题。考场上不加也不算错因为不满足题干条件加了也不会扣分。3. 从思路到代码这题的“标准答案”与最容易翻车的五个细节有了上面的思路代码其实就顺理成章了。408的算法题允许用C、C或Java描述但我建议备考期间统一用C语言练原因很简单C语言更贴近数据结构底层指针操作在考研代码题里是常态用C写出来的答案卷面最简洁阅卷老师看起来也最顺眼。3.1 先写伪代码再落成C语言如果是在考场上我会先在草稿纸上写一段伪代码确认逻辑没有漏洞再誊写到答题卡上避免涂改。1. 初始化p和q都指向链表第一个有效结点 2. 初始化计数器count为0 3. 当q不为NULL时循环 若count k则count加1 否则p指向下一个结点 q指向下一个结点 4. 若count k说明链表长度不足k返回0 5. 否则输出p的data值返回1这段伪代码最大的作用是把“q先走”“p后动”的顺序用语言固化下来写C代码的时候就不容易乱。3.2 完整C语言代码王道经典版下面是这题在王道考研系列书中收录的典型实现也是我建议你背下来的版本typedef struct LNode { int data; struct LNode *link; } LNode, *LinkList; int Search_K(LinkList list, int k) { LNode *p list-link; LNode *q list-link; int count 0; while (q ! NULL) { if (count k) { count; } else { p p-link; } q q-link; } if (count k) { return 0; } else { printf(%d, p-data); return 1; } }这段代码的时间复杂度是O(n)空间复杂度是O(1)因为只用了两个指针和一个计数器。答题的时候需要在设计思想部分明确写出这两条复杂度结论否则要扣分。3.3 最容易翻车的五个细节第一个细节p和q的初始化位置。必须是list-link也就是首元结点不能是list。带头结点的链表中list是头结点data域没有意义如果你从list开始走双指针的步数逻辑就全乱了最后p可能指向头结点输出一个未初始化的垃圾值。第二个细节q的移动必须放在p移动之后还是之前上面的代码里qp-link这个移动放在最后这样能保证count的计数和指针移动一一对应。如果你把顺序写反了比如先移动q再判断count那么count的更新会滞后一个结点最后的答案会整体错位一位。第三个细节countk的判断。很多人在循环里写成countk这会导致p提前启动一步最终指向倒数第k-1个结点。为什么是不是因为count记录的是q已经走过的步数。当q走了k步之后p才开始走这个时刻q和p之间的距离是k之后p和q同步移动p指向的正好是倒数第k个。你可以用第2.3节的模拟表验证一下。第四个细节返回值的位置。找到结点后要“输出data值并返回1”所以printf在return 1之前。如果找不到只返回0不输出任何东西。我在网上看过不少同学把printf写到while循环外面结果可能链表长度不足k时输出了一个空指针的值这是血泪教训。第五个细节如果函数原型没有给出你自己定义的时候参数类型一定要写对。头指针list的类型是LinkList也就是指向结点的指针参数int k是查找的倒数位置。有些同学把参数写成int *k纯属给自己挖坑。3.4 如果题目不给“带头结点”怎么办408真题明确规定是带头结点的单链表但很多刷题网站和模拟题会改成不带头结点。不带头结点时链表本身就是空的判断标准就是头指针为NULL所以p和q的初始化要改成LNode *p list并且函数开头加一个if(list NULL) return 0。逻辑主体和带头结点的版本完全一样。考场上如果真遇到这种变体记住核心还是双指针别被头结点的概念绕晕。4. 站在阅卷视角复盘这道题到底怎么给分怎样写才能拿满很多同学复习算法题只顾着“把代码写对”忽略了408真题其实有明确的设计思想分和复杂度分。这题不是LeetCode那种只要功能正确就AC的系统判题而是人工阅卷你的思考过程要写出来而且要写在显眼的位置。4.1 评分点拆解设计思想3分代码实现5分复杂度2分按照408历年算法大题的常见判分惯例10分左右的分值会拆成三个部分。设计思想的分值大概在3到4分要求你用文字把双指针的移动过程讲清楚。标准写法可以直接背“定义两个指针p和q初始时均指向首元结点。q先移动并设置计数器count记录q移动的步数当count小于k时p保持不动当count不小于k时q每走一步p跟着走一步。q到达链表尾部时p正好指向倒数第k个结点”。我特别提醒一句设计思想里一定要出现“倒数第k个”和“双指针”这两个关键词阅卷时间很紧张关键词被看到就能快确定位到你的思路。代码实现的分值大概在5到6分主要看几件事结点结构体定义是否正确、指针初始化是否正确、循环条件是否正确、返回条件是否完整。这个部分是最容易扣分的错一个边界条件至少扣1到2分。时间复杂度和空间复杂度的分值通常占1到2分必须写清楚“时间复杂度O(n)空间复杂度O(1)”。有些同学写了“时间复杂度为O(2n)”严格说也是常数阶但为了稳妥建议统一写成O(n)。4.2 考场上的答题顺序先写思想再写代码最后补复杂度我自己的习惯是拿到算法大题不直接动笔先在草稿纸上用一分钟把设计思想的关键词列出来然后写伪代码确认无误后誊写字迹工整的正式代码。这个流程看起来很慢实际上比边想边写在答题卡上要快得多因为你不会因为乱了逻辑而涂涂改改。答题卡上设计思想和复杂度分析写在代码前面。408阅卷是按点给分如果代码因为小错误没跑通只要设计思想表达能力准确依然能拿到相当一部分分数。反过来代码写对了但思想写不清楚扣分一样严重因为阅卷老师无法确认你是不是“蒙对的”。4.3 代码有瑕疵不等于零分三个真实扣分场景我拿三个当年的常见错误来演示一下“部分给分”的规则。第一种错误写成了两趟扫描。也就是先数长度再走n-k步。这个解法思路正确结果也能得到正确答案代码无重大语法错误一般能拿到5到7分但“尽可能高效”的那部分分数肯定没有了。第二种错误双指针思路写对了但kn时没有判断就printf。也就是说找到了错误的结点或者访问了空指针这种情况下设计思想和代码框架分还在边界处理分扣掉大概7到8分。第三种错误整段代码能跑通但忘了写时间复杂度。这种最亏代码白写了少拿1到2分。所以我在训练时对自己有一个硬性要求只要写算法题最后一行一定是空间复杂度和时间复杂度形成肌肉记忆。4.4 卷面排版的一个小建议408大题答题区域有限千万不要一上来就写一大段结构体定义。优先写核心函数结构体可以用一行typedef代替比如typedef struct LNode{int data; struct LNode *link;}LNode,*LinkList这样既不会被扣分还省空间。阅卷老师的注意力都集中在Search_K函数逻辑上别让次要代码冲淡了主题。5. 从一道题到一类题双指针在链表题里能长出一整片森林408真题虽然只有一道算法大题但这道题背后的方法论几乎可以覆盖所有常考的链表代码题。我以这题为中心把常见的延伸变体都梳理一遍。你要是在备考后期把这些变体全部手写过一遍数据结构算法大题基本就稳了。5.1 变体一查找链表的中间结点和倒数第k个的思路高度类似用快慢两个指针快指针每次走两步慢指针每次走一步。快指针到达链表尾部时慢指针正好指向中间结点。如果结点数是偶数可以约定返回靠左或靠右的那个题目一般会说明。这个变体在408里没有直接考过但它是LeetCode链表高频题面试也常问。5.2 变体二判断单链表是否存在环经典快慢指针场景。快指针每次走两步慢指针每次走一步如果链表有环两个指针一定会相遇如果无环快指针会先到达NULL。这个思路只需要O(1)的额外空间比用哈希表记录访问过的结点漂亮得多。408的大题虽然没直接考过判断环但2010年之后的408选择题里对快慢指针的理解是有可能拿来做干扰项的。5.3 变体三删除倒数第k个结点只需要在查找的基础上增加一个“前驱指针”pre。在头结点不变的情况下因为pre从list开始p从list-link开始查找结束后pre正好指向目标结点的前驱然后pre-link p-link释放p即可。这里能看出带头结点的好处删除第一个数据结点时不需要额外处理头指针变化头结点让删除操作变得统一。5.4 变体四判断两个链表是否相交两个链表如果有交点从交点开始的后半段完全相同。经典做法是分别遍历两个链表得到长度m和n让长链表的指针先走|m-n|步然后两个指针同步走第一个相等的结点就是交点。这个思路里同样有双指针的影子但用的不是快慢而是“对齐起点”的思想。408的算法题每年只考一道但你要知道一道链表题的变体完全可能以选择题的代码片段形式出现所以别抱着“考不到就不学”的心态。5.5 408算法大题的整体分布链表之外还要准备什么从2009年到近几年的真题看数据结构算法大题的命题范围大概可以分成三块线性表以链表和数组为主、树与二叉树遍历、层次结构、二叉排序树相关操作、图连通性、最短路径等。其中链表和二叉树出现的频率最高数组题目偶尔出现。如果你想在考场上做到“看到题目就能定位考点”备考时的代码积累至少要覆盖单链表的各种操作插入删除、逆置、倒数查找、合并有序链表、顺序表的各种操作循环左移、删除重复元素、二叉树的遍历先序中序后序层次、二叉排序树的构建与查找、图的基本遍历DFS和BFS。这些代码都不长每段控制在20行左右完全可以像累计单词一样背成肌肉记忆。6. 当年备考踩过的坑与408算法题的训练节奏最后聊点实在的备考经验。我见过太多人复习408算法题的方式是“在B站看视频、在App上刷选择题、在脑子里过代码”一到考场上手写就露馅。算法大题的复习只有一个标准能不能在15分钟内从空白的答题区域开始写完一段可以直接运行的手写代码。如果你做不到这个标准说明训练量还没到位。6.1 “背代码”的正确姿势不是死记是默写我当年复习数据结构时也尝试过把王道书上各种算法题的代码背下来。后来发现死背根本不可持续因为你不知道出题人会怎么改条件。正确的做法是把经典代码的“骨架”记住比如这道题你只需要记住“两个指针一个先走一个后跟计数控制启动时机”然后每次手写时重新推导细节。以这题为例我的默写流程是这样的先在草稿纸上画出一个链表随手标上k3然后模拟一遍指针怎么走动最后再动笔写代码。整个过程大约8到10分钟比拿着答案抄一遍有效十倍。6.2 真题怎么用先模拟考场再对照答案找评分点真题的价值不在于“做过一遍”而在于对照评分标准检查自己的漏洞。我建议把2009年到近五年的408真题的算法大题打印出来每道题都按正式考试的标准做一遍包括写设计思想、写代码、写复杂度分析。做完之后对照王道或天勤的参考答案把每个评分点标出来看自己到底丢在哪里分。我有一个自己用着很顺的方法每道真题做完在题目旁边记录两个数字一个是“思路耗时”一个是“代码耗时”。如果思路耗时超过5分钟说明你对这类数据结构的操作还不够熟如果代码耗时超过10分钟说明手写代码的熟练度有问题。这两个数字练到最后应该稳定在“3分钟思路7分钟代码”左右这样上了考场才会有余量。6.3 复习节奏前期重广度后期重默写速度408的复习战线很长算法大题的训练不建议一开始就每天花很多时间。我的建议是基础阶段3月到6月把王道数据结构书上的课后代码题全部看懂不需要全部默写但每道题都要能说出思路强化阶段7月到10月开始系统默写每天抽20分钟写一道经典代码题冲刺阶段11月到12月回归真题每天下午固定时间做整套真题的算法部分严格控制时间。还有一个很容易被忽略的点别只在纸上写偶尔也在编译器里跑一遍。很多细节问题比如链表指针悬空、判断条件写反是纸面检查很难发现的。我备考时每个周末都会抽半天把本周默写过的代码全部在电脑上运行验证一遍这样既能查漏补缺又能强化对代码正确性的直觉。6.4 一些工具与资源的取舍现在网上资源很多有“408快乐小网站”这种专门刷选择题的平台也有各种“hot100算法题”刷题清单还有很多人问过的“华为OD算法题刷多久能过”。我的看法是选择题刷题平台适合碎片时间用比如排队时刷几道计组选择题但算法大题必须回到纸笔因为考场是手写不是OJ判题。LeetCode Hot100和OD机试题属于招聘面试的复习范畴和408的风格不完全一样你可以用它们锻炼算法思维但别用它们替代真题训练。湖科大教书匠的计算机网络课程讲得很细适合理解网络层的各种细节但它解决的是408里计算机网络部分的简答题问题对数据结构算法大题没有直接帮助。复习时一定要分清主次算法大题只靠数据结构这一本书的代码积累就够了不需要去别的科目找补。6.5 手写代码时的心理建设很多同学一看到算法大题就心慌觉得自己代码写得不够快、不够整洁。实际上408算法大题的阅卷并没有那么苛刻只要你设计思想表达清楚、代码逻辑正确、复杂度分析准确就算字迹潦草一点、变量名起得朴素一点也不影响拿分。怕就怕在脑子里反复演练却不敢落笔考场上时间一晃而过最后只留下一段残缺的半成品代码。我个人的习惯是不管题目多简单先写函数原型再写循环框架最后补充边界条件。这个顺序能保证你即使时间不够也能拿到函数设计和循环主体的部分分而不是在纠结变量命名上浪费宝贵的几分钟。回头看这道2009年的408算法题它表面上只考了一个双指针技术实际上检验的是你能否把一个看似简单的数据结构问题考虑周全。我个人做完这道题的最大收获并不是背下来那八行代码而是彻底明白了“边界条件”这四个字的重量。k等于1怎么办k比链表还长怎么办链表空怎么办头结点要不要跳过每一个问题背后都是真实的手写代码经验。408的算法题从来没有所谓的高端技巧它考验的就是你对基础知识掌握的颗粒度。把这道题吃透然后继续往下走后面再遇到链表、二叉树、图的任何算法大题你都会有一种“这题我见过”的底气。
408经典算法题：双指针查找单链表倒数第k个结点
如果你手头有2009年的408真题翻到数据结构部分最后那道算法大题大概率会看到一个熟悉得不能再熟悉的面孔带头结点单链表查找倒数第k个结点的位置。我第一次做这道题的时候心里想的是这还不简单先数一遍链表有几个结点再正着走到第n-k1个不就行了。结果一对参考答案就发现出题人在题干里写的“尽可能高效”五个字才是这道题真正的考点所在。2009年是408统考的第一年这道算法题基本奠定了后来十几年408算法大题的出题风格不考偏题怪题考的就是基础数据结构的边界意识和算法设计能力。对准备考研408的同学来说这题是绕不开的入门题对只刷LeetCode Hot100、或者在准备华为OD机试的同学来说这也是双指针思想在链表上最朴素也最典型的一次应用。这篇文章我就把这题从审题、推演、写码到判卷全部掰开揉碎讲一遍看完你不仅能拿下这道题还能顺便把链表双指针这一类题都吃透。1. 题目到底问什么2009年408链表题的精确描述与三个隐藏考点先花30秒把当年的题目完整看一遍很多同学做题做错不是因为代码能力不行而是题干都没读透。已知一个带头结点的单链表结点结构为(data, link)该链表只给出了头指针list。在不改变链表的前提下请设计一个尽可能高效的算法查找链表中倒数第kk为正整数个位置上的结点。若查找成功算法输出该结点的data域的值并返回1否则只返回0。要求描述算法的基本设计思想。根据设计思想采用C或C或Java语言描述算法关键之处给出注释。说明算法的时间复杂度和空间复杂度。这道题属于408数据结构部分的大题分值大概在8到10分之间设计思想、代码实现、复杂度分析三个维度都有对应的给分点。第一次做这题的人很容易犯一个相同的错误上来就写代码忽略了题目里的“尽可能高效”。1.1 这三个隐藏考点是拿满分的分水岭第一个隐藏考点是“带头结点”。带头结点意味着链表的第一个有效数据结点是list-link而不是list本身。很多参考答案和经典教材里指针的初始化都是从list-link开始的你要是从list开始移动最后输出的data值就是头结点里那段未初始化的垃圾数据整个结果完全不可控。第二个隐藏考点是“不改变链表”。这句话可以直接理解为你不能把链表倒置不能交换结点位置连改指针方向都不行。我见过有同学想“先把链表反转再查第k个”这种思路在时间复杂度上可能勉强过得去但直接违反了题干约束就算代码写出来也不得分。第三个隐藏考点是“尽可能高效”。这里的高效主要指的是时间复杂度。单链表只能从前往后遍历如果你先用一趟扫描求出链表长度n再从头走n-k步找到目标结点这个算法的时间复杂度严格说是O(n)但它扫描了两次链表。在408的语境里更优的解法应该是一趟扫描完成也就是双指针法。后面我会具体证明为什么双指针是这道题的标准答案。1.2 为什么这道题能成为408的“压舱石”题目2009年这道题之后408的数据结构算法大题几乎每年都保持类似的命题思路要么考链表要么考二叉树偶尔考数组和栈队列但核心永远是“用最朴素的算法操作最基础的数据结构并给出严格的时间和空间复杂度分析”。这道题之所以被各大考研机构收录为经典是因为它精准踩中了三个常考能力一是对单链表逻辑结构的理解二是对双指针这种优化手段的灵活运用三是对边界条件的防御性思考。可以说把这一题吃透考研408数据结构部分最大的那道题你就有了一个基本盘。2. 从“数长度再走一遍”到双指针两种解法的完整推演在讲标准答案之前我先把大部分人的第一反应展开讲透因为这也是评分标准里非常重要的参照系。只有知道常规解法输在哪里你才能理解双指针解法赢在哪里。2.1 常规解法两次遍历思路简单但不够“高效”假设链表有n个结点。第一次遍历从头走到尾数出n是多少。目标结点是倒数第k个也就是正数第n-k1个。第二次遍历从头开始走每走一步计数加1走到第n-k1个结点就是答案。这个思路本身没有任何错误甚至在k非常接近1或n的时候代码写起来比双指针还要直观。但它的问题在于链表是单向的第二次遍历必须从头开始走如果链表很长比如有100万个结点你要先完整走一遍数长度再从头走一遍找位置总共移动约100万加100万减k次指针。对于“只查一次”的场景来说这其实也能接受但题目明确要求“尽可能高效”所以这个解法只能算合格不能算优秀。从考场的角度说如果实在想不出双指针写这个解法也能拿到一定的分尤其是设计思想表达清楚、代码无语法错误的话通常能拿到基础分。但你要是想冲击满分必须学会双指针。2.2 双指针解法让两个指针保持k-1的间距双指针的思路并不复杂用一个场景类比你就明白了。想象你和一个朋友在一条单行道上走你让他先走k步然后停下来等你等你跟上他之后你们俩保持同步往前走。当他走到路的尽头不能再走时你所站的位置就是从后往前数的第k个位置。对应到链表上就是设两个指针p和q初始都指向链表的首元结点也就是list-link。q先移动同时用一个计数器count记录q已经走过的步数。当count小于k的时候只有q移动p不动一旦count不小于k也就是q已经领先了k步之后q每移动一步p也跟着移动一步。这样当q走到了链表末尾的NULL时p正好指向倒数第k个结点。这个算法的精妙之处在于两个指针虽然是都从头走到尾但它们是在同一趟遍历中完成的。q走完整个链表需要n步p在q走了k步之后才开始走总共走了n-k步两个指针的移动总数是n加n-k也就是2n-k时间复杂度仍然是O(n)但整个过程只有一趟扫描。这就是“尽可能高效”的题眼所在。2.3 一个具体例子的完整走位过程为了把双指针的原理彻底讲清楚我手动模拟一个例子。假设链表有10个结点结点的data值依次是1、2、3、4、5、6、7、8、9、10我们要找倒数第3个结点正确答案应该是数据的8的那个结点因为它正数第8个倒数第3个。n10k3一开始p和q都指向data1的结点count0。q开始移动q的步数count的值p的位置第1步count变为1还在data1第2步count变为2还在data1第3步count变为3还在data1第4步count3q继续走data2第5步count3q继续走data3第6步count3q继续走data4第7步count3q继续走data5第8步count3q继续走data6第9步count3q继续走data7第10步count3q继续走data8当q走到第10步时q指向data9的结点。q再移动一步就到NULLp继续走到data8的结点。此时qNULL循环结束p指向data8的结点正好是倒数第3个。整个走位过程一目了然这个表也是你在答题时可以写在草稿纸上帮助自己理清逻辑的。2.4 边界条件为什么这道题的坑全在边界上双指针的代码框架不难难的是把边界条件处理完整。我按照408阅卷的常见标准把边界情况一个个列出来k1指的是最后一个结点。按照上面的走位q到头时p正好指向最后一个结点正确。kn指的是第一个结点。q从首元结点走n步到NULLp在count等于n之前一直不动直到倒数第n步才刚起步最后q到NULL时p还在首元结点正确。kn也就是k比链表长度还大。此时q已经走完了整个链表到NULLcount始终小于k循环结束后通过if(countk)返回0正确。空链表也就是只有头结点。p和q都指向NULLwhile循环一次都不执行count0k是正整数countk成立返回0正确。k0题目已经说明k是正整数所以原始答案里一般不处理这种情况。但如果你在写工程代码应该在函数开头加一个if(k0) return 0防止k0时出现p-data访问空指针的问题。考场上不加也不算错因为不满足题干条件加了也不会扣分。3. 从思路到代码这题的“标准答案”与最容易翻车的五个细节有了上面的思路代码其实就顺理成章了。408的算法题允许用C、C或Java描述但我建议备考期间统一用C语言练原因很简单C语言更贴近数据结构底层指针操作在考研代码题里是常态用C写出来的答案卷面最简洁阅卷老师看起来也最顺眼。3.1 先写伪代码再落成C语言如果是在考场上我会先在草稿纸上写一段伪代码确认逻辑没有漏洞再誊写到答题卡上避免涂改。1. 初始化p和q都指向链表第一个有效结点 2. 初始化计数器count为0 3. 当q不为NULL时循环 若count k则count加1 否则p指向下一个结点 q指向下一个结点 4. 若count k说明链表长度不足k返回0 5. 否则输出p的data值返回1这段伪代码最大的作用是把“q先走”“p后动”的顺序用语言固化下来写C代码的时候就不容易乱。3.2 完整C语言代码王道经典版下面是这题在王道考研系列书中收录的典型实现也是我建议你背下来的版本typedef struct LNode { int data; struct LNode *link; } LNode, *LinkList; int Search_K(LinkList list, int k) { LNode *p list-link; LNode *q list-link; int count 0; while (q ! NULL) { if (count k) { count; } else { p p-link; } q q-link; } if (count k) { return 0; } else { printf(%d, p-data); return 1; } }这段代码的时间复杂度是O(n)空间复杂度是O(1)因为只用了两个指针和一个计数器。答题的时候需要在设计思想部分明确写出这两条复杂度结论否则要扣分。3.3 最容易翻车的五个细节第一个细节p和q的初始化位置。必须是list-link也就是首元结点不能是list。带头结点的链表中list是头结点data域没有意义如果你从list开始走双指针的步数逻辑就全乱了最后p可能指向头结点输出一个未初始化的垃圾值。第二个细节q的移动必须放在p移动之后还是之前上面的代码里qp-link这个移动放在最后这样能保证count的计数和指针移动一一对应。如果你把顺序写反了比如先移动q再判断count那么count的更新会滞后一个结点最后的答案会整体错位一位。第三个细节countk的判断。很多人在循环里写成countk这会导致p提前启动一步最终指向倒数第k-1个结点。为什么是不是因为count记录的是q已经走过的步数。当q走了k步之后p才开始走这个时刻q和p之间的距离是k之后p和q同步移动p指向的正好是倒数第k个。你可以用第2.3节的模拟表验证一下。第四个细节返回值的位置。找到结点后要“输出data值并返回1”所以printf在return 1之前。如果找不到只返回0不输出任何东西。我在网上看过不少同学把printf写到while循环外面结果可能链表长度不足k时输出了一个空指针的值这是血泪教训。第五个细节如果函数原型没有给出你自己定义的时候参数类型一定要写对。头指针list的类型是LinkList也就是指向结点的指针参数int k是查找的倒数位置。有些同学把参数写成int *k纯属给自己挖坑。3.4 如果题目不给“带头结点”怎么办408真题明确规定是带头结点的单链表但很多刷题网站和模拟题会改成不带头结点。不带头结点时链表本身就是空的判断标准就是头指针为NULL所以p和q的初始化要改成LNode *p list并且函数开头加一个if(list NULL) return 0。逻辑主体和带头结点的版本完全一样。考场上如果真遇到这种变体记住核心还是双指针别被头结点的概念绕晕。4. 站在阅卷视角复盘这道题到底怎么给分怎样写才能拿满很多同学复习算法题只顾着“把代码写对”忽略了408真题其实有明确的设计思想分和复杂度分。这题不是LeetCode那种只要功能正确就AC的系统判题而是人工阅卷你的思考过程要写出来而且要写在显眼的位置。4.1 评分点拆解设计思想3分代码实现5分复杂度2分按照408历年算法大题的常见判分惯例10分左右的分值会拆成三个部分。设计思想的分值大概在3到4分要求你用文字把双指针的移动过程讲清楚。标准写法可以直接背“定义两个指针p和q初始时均指向首元结点。q先移动并设置计数器count记录q移动的步数当count小于k时p保持不动当count不小于k时q每走一步p跟着走一步。q到达链表尾部时p正好指向倒数第k个结点”。我特别提醒一句设计思想里一定要出现“倒数第k个”和“双指针”这两个关键词阅卷时间很紧张关键词被看到就能快确定位到你的思路。代码实现的分值大概在5到6分主要看几件事结点结构体定义是否正确、指针初始化是否正确、循环条件是否正确、返回条件是否完整。这个部分是最容易扣分的错一个边界条件至少扣1到2分。时间复杂度和空间复杂度的分值通常占1到2分必须写清楚“时间复杂度O(n)空间复杂度O(1)”。有些同学写了“时间复杂度为O(2n)”严格说也是常数阶但为了稳妥建议统一写成O(n)。4.2 考场上的答题顺序先写思想再写代码最后补复杂度我自己的习惯是拿到算法大题不直接动笔先在草稿纸上用一分钟把设计思想的关键词列出来然后写伪代码确认无误后誊写字迹工整的正式代码。这个流程看起来很慢实际上比边想边写在答题卡上要快得多因为你不会因为乱了逻辑而涂涂改改。答题卡上设计思想和复杂度分析写在代码前面。408阅卷是按点给分如果代码因为小错误没跑通只要设计思想表达能力准确依然能拿到相当一部分分数。反过来代码写对了但思想写不清楚扣分一样严重因为阅卷老师无法确认你是不是“蒙对的”。4.3 代码有瑕疵不等于零分三个真实扣分场景我拿三个当年的常见错误来演示一下“部分给分”的规则。第一种错误写成了两趟扫描。也就是先数长度再走n-k步。这个解法思路正确结果也能得到正确答案代码无重大语法错误一般能拿到5到7分但“尽可能高效”的那部分分数肯定没有了。第二种错误双指针思路写对了但kn时没有判断就printf。也就是说找到了错误的结点或者访问了空指针这种情况下设计思想和代码框架分还在边界处理分扣掉大概7到8分。第三种错误整段代码能跑通但忘了写时间复杂度。这种最亏代码白写了少拿1到2分。所以我在训练时对自己有一个硬性要求只要写算法题最后一行一定是空间复杂度和时间复杂度形成肌肉记忆。4.4 卷面排版的一个小建议408大题答题区域有限千万不要一上来就写一大段结构体定义。优先写核心函数结构体可以用一行typedef代替比如typedef struct LNode{int data; struct LNode *link;}LNode,*LinkList这样既不会被扣分还省空间。阅卷老师的注意力都集中在Search_K函数逻辑上别让次要代码冲淡了主题。5. 从一道题到一类题双指针在链表题里能长出一整片森林408真题虽然只有一道算法大题但这道题背后的方法论几乎可以覆盖所有常考的链表代码题。我以这题为中心把常见的延伸变体都梳理一遍。你要是在备考后期把这些变体全部手写过一遍数据结构算法大题基本就稳了。5.1 变体一查找链表的中间结点和倒数第k个的思路高度类似用快慢两个指针快指针每次走两步慢指针每次走一步。快指针到达链表尾部时慢指针正好指向中间结点。如果结点数是偶数可以约定返回靠左或靠右的那个题目一般会说明。这个变体在408里没有直接考过但它是LeetCode链表高频题面试也常问。5.2 变体二判断单链表是否存在环经典快慢指针场景。快指针每次走两步慢指针每次走一步如果链表有环两个指针一定会相遇如果无环快指针会先到达NULL。这个思路只需要O(1)的额外空间比用哈希表记录访问过的结点漂亮得多。408的大题虽然没直接考过判断环但2010年之后的408选择题里对快慢指针的理解是有可能拿来做干扰项的。5.3 变体三删除倒数第k个结点只需要在查找的基础上增加一个“前驱指针”pre。在头结点不变的情况下因为pre从list开始p从list-link开始查找结束后pre正好指向目标结点的前驱然后pre-link p-link释放p即可。这里能看出带头结点的好处删除第一个数据结点时不需要额外处理头指针变化头结点让删除操作变得统一。5.4 变体四判断两个链表是否相交两个链表如果有交点从交点开始的后半段完全相同。经典做法是分别遍历两个链表得到长度m和n让长链表的指针先走|m-n|步然后两个指针同步走第一个相等的结点就是交点。这个思路里同样有双指针的影子但用的不是快慢而是“对齐起点”的思想。408的算法题每年只考一道但你要知道一道链表题的变体完全可能以选择题的代码片段形式出现所以别抱着“考不到就不学”的心态。5.5 408算法大题的整体分布链表之外还要准备什么从2009年到近几年的真题看数据结构算法大题的命题范围大概可以分成三块线性表以链表和数组为主、树与二叉树遍历、层次结构、二叉排序树相关操作、图连通性、最短路径等。其中链表和二叉树出现的频率最高数组题目偶尔出现。如果你想在考场上做到“看到题目就能定位考点”备考时的代码积累至少要覆盖单链表的各种操作插入删除、逆置、倒数查找、合并有序链表、顺序表的各种操作循环左移、删除重复元素、二叉树的遍历先序中序后序层次、二叉排序树的构建与查找、图的基本遍历DFS和BFS。这些代码都不长每段控制在20行左右完全可以像累计单词一样背成肌肉记忆。6. 当年备考踩过的坑与408算法题的训练节奏最后聊点实在的备考经验。我见过太多人复习408算法题的方式是“在B站看视频、在App上刷选择题、在脑子里过代码”一到考场上手写就露馅。算法大题的复习只有一个标准能不能在15分钟内从空白的答题区域开始写完一段可以直接运行的手写代码。如果你做不到这个标准说明训练量还没到位。6.1 “背代码”的正确姿势不是死记是默写我当年复习数据结构时也尝试过把王道书上各种算法题的代码背下来。后来发现死背根本不可持续因为你不知道出题人会怎么改条件。正确的做法是把经典代码的“骨架”记住比如这道题你只需要记住“两个指针一个先走一个后跟计数控制启动时机”然后每次手写时重新推导细节。以这题为例我的默写流程是这样的先在草稿纸上画出一个链表随手标上k3然后模拟一遍指针怎么走动最后再动笔写代码。整个过程大约8到10分钟比拿着答案抄一遍有效十倍。6.2 真题怎么用先模拟考场再对照答案找评分点真题的价值不在于“做过一遍”而在于对照评分标准检查自己的漏洞。我建议把2009年到近五年的408真题的算法大题打印出来每道题都按正式考试的标准做一遍包括写设计思想、写代码、写复杂度分析。做完之后对照王道或天勤的参考答案把每个评分点标出来看自己到底丢在哪里分。我有一个自己用着很顺的方法每道真题做完在题目旁边记录两个数字一个是“思路耗时”一个是“代码耗时”。如果思路耗时超过5分钟说明你对这类数据结构的操作还不够熟如果代码耗时超过10分钟说明手写代码的熟练度有问题。这两个数字练到最后应该稳定在“3分钟思路7分钟代码”左右这样上了考场才会有余量。6.3 复习节奏前期重广度后期重默写速度408的复习战线很长算法大题的训练不建议一开始就每天花很多时间。我的建议是基础阶段3月到6月把王道数据结构书上的课后代码题全部看懂不需要全部默写但每道题都要能说出思路强化阶段7月到10月开始系统默写每天抽20分钟写一道经典代码题冲刺阶段11月到12月回归真题每天下午固定时间做整套真题的算法部分严格控制时间。还有一个很容易被忽略的点别只在纸上写偶尔也在编译器里跑一遍。很多细节问题比如链表指针悬空、判断条件写反是纸面检查很难发现的。我备考时每个周末都会抽半天把本周默写过的代码全部在电脑上运行验证一遍这样既能查漏补缺又能强化对代码正确性的直觉。6.4 一些工具与资源的取舍现在网上资源很多有“408快乐小网站”这种专门刷选择题的平台也有各种“hot100算法题”刷题清单还有很多人问过的“华为OD算法题刷多久能过”。我的看法是选择题刷题平台适合碎片时间用比如排队时刷几道计组选择题但算法大题必须回到纸笔因为考场是手写不是OJ判题。LeetCode Hot100和OD机试题属于招聘面试的复习范畴和408的风格不完全一样你可以用它们锻炼算法思维但别用它们替代真题训练。湖科大教书匠的计算机网络课程讲得很细适合理解网络层的各种细节但它解决的是408里计算机网络部分的简答题问题对数据结构算法大题没有直接帮助。复习时一定要分清主次算法大题只靠数据结构这一本书的代码积累就够了不需要去别的科目找补。6.5 手写代码时的心理建设很多同学一看到算法大题就心慌觉得自己代码写得不够快、不够整洁。实际上408算法大题的阅卷并没有那么苛刻只要你设计思想表达清楚、代码逻辑正确、复杂度分析准确就算字迹潦草一点、变量名起得朴素一点也不影响拿分。怕就怕在脑子里反复演练却不敢落笔考场上时间一晃而过最后只留下一段残缺的半成品代码。我个人的习惯是不管题目多简单先写函数原型再写循环框架最后补充边界条件。这个顺序能保证你即使时间不够也能拿到函数设计和循环主体的部分分而不是在纠结变量命名上浪费宝贵的几分钟。回头看这道2009年的408算法题它表面上只考了一个双指针技术实际上检验的是你能否把一个看似简单的数据结构问题考虑周全。我个人做完这道题的最大收获并不是背下来那八行代码而是彻底明白了“边界条件”这四个字的重量。k等于1怎么办k比链表还长怎么办链表空怎么办头结点要不要跳过每一个问题背后都是真实的手写代码经验。408的算法题从来没有所谓的高端技巧它考验的就是你对基础知识掌握的颗粒度。把这道题吃透然后继续往下走后面再遇到链表、二叉树、图的任何算法大题你都会有一种“这题我见过”的底气。