2009年408考研算法真题深度复盘：链表倒数第k个结点的快慢指针解法

如果你准备过408考研2009年那道算法大题应该是绕不开的。它几乎是每一本408真题资料里都会第一个开讲的链表题也是很多人第一次真正意识到“算法题不是背代码”这个道理的地方。这篇文章就来完整复盘这道题把考点定位、思路推导、标准代码、常见错误以及它对后续复习的价值一次讲清楚。当年这道题之所以被反复提起首先因为2009年是408计算机学科专业基础综合统考的第一年命题组还在摸索风格题目普遍偏基础却已经把“数据结构算法设计题”的基本套路亮了出来给定一个经典结构要求设计一个时间上尽可能高效的算法并完成从思想、步骤到代码的全过程书写。这一套要求后来成了408每年最后那道算法综合题的固定模板。对于现在刷题备考的同学来说吃透这一道题等于提前熟悉了考研算法大题的整个游戏规则。1. 2009年408算法题到底考了什么1.1 原题还原与当年考场上的真实处境为了避免大家去翻旧书我把这道题的题干完整还原在这里已知一个带有表头结点的单链表结点结构为data、link假设该链表只给出了头指针list。在不改变链表的前提下请设计一个尽可能高效的算法查找链表中倒数第 k 个位置上的结点k 为正整数。若查找成功算法输出该结点的data域的值并返回 1否则只返回 0。要求描述算法的基本设计思想描述算法的详细实现步骤根据设计思想和实现步骤采用 C、C 或 Java 语言描述算法关键之处给出简要注释。这个题干里有几个信息值得划重点。第一“带有表头结点”说明链表有一个不存数据的头结点真实数据从list-link开始。第二“不改变链表”直接否掉了那种“先把链表反转再数第 k 个”的思路。第三“尽可能高效”这句话是整道题的题眼如果一开始只想到了遍历两遍的做法即使代码写得全对也不是标准答案想要的最优解。当年的考场环境和现在很不一样没有 LeetCode没有 IDE甚至连代码都是在答题卡上手写。考生需要在有限时间内同时完成“思路描述、步骤描述、代码实现”三件事这种三段式书写本身就需要刻意训练。很多同学第一遍做这道题时思路可能一分钟就想通了真正动手写代码却卡在边界条件上最后丢分丢得很冤枉。1.2 这道题的考点定位数据结构大纲里的哪个角落从408考纲来看这道题对应的是“数据结构”部分“线性表”章节中的“链式存储结构”具体考查点可以拆成四层。第一层是链表的基本操作。能够正确遍历单链表、判断结点是否为空、通过link指针移动这是最基础的要求。很多同学平时在 IDE 里写链表题没有感觉一到手写就经常忘记判断空指针或者把头结点的处理弄错。第二层是算法设计能力。题目没有直接说“用双指针”而是让你自己设计一个“尽可能高效”的算法。这考查的是能不能从“倒数第 k 个结点”这个需求里抽象出“两个指针保持固定距离同步移动”的模型。第三层是复杂度分析。标准解法的时间复杂度是 O(n)空间复杂度是 O(1)。题目里“尽可能高效”其实就是要求你用 O(n) 时间、O(1) 空间解决问题。如果用了辅助数组存结点地址空间复杂度变成 O(n)在阅卷时会被扣分。第四层是代码规范与边界判断。能不能正确处理 k 大于链表长度、k 等于链表长度、链表只有头结点、链表只有一个数据结点等边界情况是区分“会背代码”和“真正理解”的关键。1.3 为什么说它是最具代表性的一道408算法题这道题被所有资料放在链表题型第一个讲不是没有原因的。它几乎没有用到任何高深的数据结构不像平衡二叉树、图论算法那样有复杂的调整过程整个算法的核心只有两个指针加一个循环却把算法题所有核心要素全装进去了。它有一道好算法题该有的全部特征问题描述简单所有人都能看懂暴力解法容易想到但不够最优最优解法需要一点技巧一旦点破又觉得理所当然边界条件丰富测试用例可以写出七八个代码量短适合手写和阅卷。这样的题目非常适合用来考察考生的算法基本功和思维灵活性。另一方面这道题也奠定了408算法大题的基本风格不追求偏题怪题而是在经典结构上做文章让你在有限时间内设计一个高效的算法。这种风格延续至今所以直到今天每年考研群里讨论408算法题时2009年这道题依然会被翻出来当作入门范例。2. 从暴力解到最优解解题思路的完整推导2.1 最容易想到的思路先求表长再数倒数第k个单链表是单向的结点只有指向后继的指针没有指向前驱的指针。所以“倒数第 k 个结点”不是直接能访问到的必须从头开始找。于是最自然的想法就出现了先遍历一遍链表数出链表长度 n然后再从头开始走 n-k 步停在的那个结点就是倒数第 k 个结点。用生活里的例子类比就像一条单向通行的队伍你要找倒数第 3 个人。你不能从队尾往前数因为你不知道队尾在哪里也不知道队伍多长。所以你先从队头走到队尾数清楚一共多少人然后再从头重新走一遍走到倒数第 3 个位置停下来。这个思路正确吗完全正确。代码写出来也不难两个循环就搞定。但问题出在“尽可能高效”这四个字上。这种解法虽然时间复杂度也是 O(n)但实际上遍历了两遍链表当链表长度 n 非常大的时候时间成本接近最优解的两倍。在408的评分标准里这个解法通常会被扣掉一个档次的分数因为题目明确要求“尽可能高效”而你给出的并不是最优方案。2.2 快慢指针的核心思想让两个指针保持固定距离最优解是快慢指针也叫双指针思路其实非常朴素两个指针同时从第一个数据结点出发快指针先走 k 步然后两个指针以相同的速度同步往后移动。当快指针走到链表末尾的 NULL 时慢指针所在的位置恰好就是倒数第 k 个结点。回到排队那个例子你不知道队伍有多长但你可以找两个人让第一个人从队头先往前数出 k 个人然后两个人保持这个距离一起往前走。当第一个人走到队尾身后时第二个人站的位置就是倒数第 k 个人。两个人之间的距离始终是 k这个“距离感”是解题的关键。为什么快指针走 k 步后两个指针的间距正好等于 k 个结点因为快指针从第 1 个结点出发走 k 步后到达第 k1 个结点慢指针还在第 1 个结点两个指针之间正好隔了 k 个结点。之后两个指针同步移动距离始终保持不变。当快指针到达 NULL 时慢指针就在倒数第 k 个结点上。2.3 边界条件与正确性证明要写出正确的代码光知道思路还不够必须把边界条件想清楚。这里我用一个简单的代数推导来说明解法为什么成立。假设链表长度为 n数据结点个数。快指针 q 先走 k 步分两种情况。第一种如果 q 在走完 k 步之前就遇到了 NULL说明 k 大于 n链表中根本不存在倒数第 k 个结点此时直接返回 0。第二种如果 q 成功走完 k 步此时 q 指向第 k1 个结点慢指针 p 指向第 1 个结点两者距离为 k。接下来让 p 和 q 同步走当 q 到达 NULL 时q 一共又走了 n-k 步。p 也从第 1 个结点移动了 n-k 步到达第 (n-k)1 n-k1 个结点。从链表末尾往前数第 n-k1 个结点正好是倒数第 k 个结点。这个推导还能帮助我们写出正确的循环终止条件。有些同学喜欢让快指针先走 k-1 步然后判断“当 q-link 为 NULL 时 p 指向倒数第 k 个结点”这种写法也可以但边界条件更隐蔽容易出错。我更推荐先走 k 步、以 q 是否为 NULL 作为循环终止条件的写法因为 NULL 的判断比 q-link 的判断更直观也不容易在 k 的取值上犯糊涂。边界情况至少要想清楚这几组k 大于链表长度时返回 0k 恰好等于链表长度时处理结果应该是第一个数据结点链表只有一个数据结点且 k1 时处理结果应该是这个结点本身链表只有头结点没有任何数据结点时任何正整数 k 都应该返回 0。这些情况在代码里其实都被统一的逻辑覆盖了但如果你心里没有提前过一遍写代码时很容易在某一个分支上踩坑。3. 标准答案级代码实现与逐行精讲3.1 数据结构定义与函数原型先看题目给出的结点结构。这里有一个特别容易忽视的细节题目里链表的指针字段叫link不叫next。很多同学平时写惯了next考试时直接照搬自己的习惯写p-next虽然算法思想是对的但和题目给出的结构不一致阅卷时会显得很不严谨。所以老老实实按照题目的定义来写typedef struct node { int data; struct node *link; } NODE;函数原型按题目要求设计为int Search_k(NODE *list, int k);传入头指针和正整数 k查找成功输出data并返回 1查找失败返回 0。注意这里有输出动作所以代码里除了 return还要在成功分支调用printf输出结点值。3.2 完整C代码实现下面是完整的参考实现我加了必要的注释。这段代码可以做到只遍历一遍链表时间复杂度 O(n)空间复杂度 O(1)并且正确处理了 k 大于链表长度的情况。// list 是带头结点的单链表头指针k 为正整数 int Search_k(NODE *list, int k) { // p 和 q 都从第一个数据结点开始 NODE *p list-link; NODE *q list-link; int count 0; // 如果 k 不是正整数按错误输入处理 if (k 0) { return 0; } // 快指针 q 先走 k 步 while (q ! NULL count k) { q q-link; count; } // 如果 q 提前走到 NULL说明链表长度小于 k if (count k) { return 0; } // p 和 q 同步移动q 到达 NULL 时p 指向倒数第 k 个结点 while (q ! NULL) { p p-link; q q-link; } // 输出结点值并返回成功标志 printf(%d, p-data); return 1; }这段代码里有一个值得记住的小技巧在第一个 while 循环里我同时判断了q ! NULL和count k这样如果链表长度不够循环会因为q NULL提前退出退出后通过检查count k就能发现长度不够。这种写法比单纯用 for 循环走 k 步更安全不需要提前计算链表长度就能避免空指针访问。3.3 代码细节的得分点和失分点代码本身不长但可以抠的细节很多。第一个失分点是变量初始化。p 和 q 必须从list-link也就是第一个数据结点开始而不是从list本身开始。如果从list开始相当于把头结点也算进去了最后定位的结点会比正确答案多偏移一个位置。这个问题在手工模拟链表时特别容易发现但很多人在考场上一紧张就会忽略。第二个失分点是没有处理 k 大于链表长度的情况。如果不加if (count k) return 0;那么当快指针 q 因为走到 NULL 而退出循环后程序会直接进入第二个 while 循环而此时 q 已经是 NULL第二个循环根本不会执行最终 p 指向的还是第一个数据结点但此时整个查找应该返回失败。更严重的是如果链表本身为空只有头结点p 一开始就是 NULL最后printf(%d, p-data)会访问空指针直接崩溃。所以加一个count k的判断能同时解决两处隐患。第三个得分点是对非正整数 k 的防御。题目明确说 k 是正整数所以严格来说不判断 k0 也可以但写上这个判断会让代码更严谨。阅卷老师看到这种细节会认为你考虑问题比较全面。当然如果你担心多写了反而画蛇添足不写也不算错毕竟题目已经限定了 k 为正整数。第四个得分点是使用常量辅助空间。全程只用了一个额外的变量 count 和两个指针 p、q空间复杂度是 O(1)。没有任何数组、链表复制或者递归调用这才是“高效”的真正体现。我把这段代码和其他常见写法做过对比有一种写法是快指针先走 k-1 步进入循环循环条件是while (q-link ! NULL)走到 q 指向最后一个结点时 p 正好是倒数第 k 个。这种写法的优点是循环次数稍微少一点但它的边界判断依赖于q-link如果 q 是 NULL访问q-link会直接报错。所以在 k 大于链表长度的场景下必须额外插入一段防御代码。相比之下先走 k 步再判断 q 是否为 NULL 的写法更干净也更适合在考场上快速写完。4. 阅卷启示这道题暴露的几类常见错误4.1 常见错误清单我把历年考生在这道题上最容易犯的错误整理成了一个表你可以对照检查自己的代码有没有踩中过。错误类型错误做法后果扣分程度指针起始位置错误p 和 q 从list开始而不是list-link结果整体偏移一个结点严重结果不对没有防御 k 大于链表长度快指针走 k 步时遇到 NULL 后继续执行可能返回错误结果或访问空指针严重可能代码直接崩溃使用两遍遍历先求长度 n再走 n-k 步正确但不是最优一般扣 2 分左右使用辅助数组存储结点遍历一遍存地址再取下标空间复杂度不满足要求扣分较多改变链表结构先反转链表再找第 k 个违反题目“不改变链表”要求完全不得分输出位置错误在成功分支忘了printf或者失败分支也输出不符合题目要求视情况扣分这里我想重点说两遍遍历和辅助数组这两个错误。它们的共同点是算法本身能得出正确答案但不是“尽可能高效”。在408的评分逻辑里题目明确要求“尽可能高效”如果你给的不是最优解老师会认为你对“高效”的理解不到位扣分是必然的。但也不用恐慌大多数阅卷标准对这种解法不会全扣因为答题者展示出了基本的逻辑能力只是优化意识不足。4.2 当年评分标准的一次复盘很多辅导书上贴过这道题的评分要点大致是这么分配的基本设计思想是否正确占一部分分数实现步骤描述是否清晰占一部分分数代码实现是否正确、完整、高效占最大一部分分数。这意味着只要你把思路和步骤写清楚即使代码有一处致命错误也不会得零分。反过来如果你只写了一坨代码没有任何思路说明和步骤描述即使代码完全正确也可能拿不满分数。因为阅卷老师需要从你的文字描述里判断你是不是真的理解了这个算法而不是背了一篇答案。所以从平时练习开始就要养成“先写思想再写步骤最后写代码”的习惯。这个三段式答题结构本身就是408算法大题独特的地方。它不像 LeetCode 那样只看代码正确性而是要求你把思维过程显式地写出来。很多刷题刷得多的同学第一次做408真题会不太适应因为 LeetCode 上是“写出来并运行通过”而408上是“讲清楚并且写对”后者对表达能力的要求更高。4.3 对现在刷题备考的直接影响现在很多同学刷题喜欢直接用代码编辑器写完一跑通过了就下一题。这种习惯对准备408来说是不够的。408算法大题需要的是“手写能力文字表达能力”的组合而这两种能力只有通过手写和复述才能练出来。我的建议是像2009年这道题这样重量级的真题至少应该在纸上完整默写过三遍。第一遍照着答案抄理解每一行代码为什么这么写第二遍合上答案自己写同时把思路和步骤用中文写出来第三遍完全模拟考场给自己限时15分钟从读题到写完代码一步到位。三遍下来你不仅熟悉了这道题也熟悉了408算法大题的答题节奏。另外这道题里包含的“双指针”思想在后续很多题目里都会复用。比如判断链表是否有环的快慢指针、链表中点问题、链表倒数第 k 个结点问题本质上都是同一个技巧的变体。所以与其说2009年这道题是一道孤立的真题不如说它是一个思想种子种下去以后还能长出一片树林。5. 从2009年到现在这道题带出的复习方法论5.1 真题变体与扩展练习方向理解双指针以后可以做几个针对性的变体练习。第一个是LeetCode第19题“删除链表的倒数第N个结点”这题把“查找”变成了“查找并删除”需要维护一个 prev 指针或者用哑结点来处理头结点被删的情况。第二个是LeetCode第876题“链表的中间结点”快指针每次走两步、慢指针走一步快指针到尾时慢指针在中点。第三个是“判断链表是否有环”的经典题快慢指针一个走两步一个走一步如果有环它们一定会相遇。做这些变体题不是为了刷数量而是为了把一个模型吃透。双指针的世界里有两个基本操作一是快慢速度不同二是快慢起点不同。2009年这道题属于“起点不同、速度相同”LeetCode第876题属于“起点相同、速度不同”判断环属于“一个跑得快一个跑得慢并在循环中判断相遇”。把这三个变体放在一起对比你会对双指针有更深的理解。如果目标就是408我不太建议花大量时间在偏怪难的 LeetCode 题上。408算法大题的风格是基础、经典、代码量适中把真题和真题改编题吃透比盲目刷几百道题更划算。天勤、王道等资料里针对链表部分的题都值得做尤其是那些要求“时间上尽可能高效”的题目做的时候要主动去和最优解对比而不是写出来能跑就算完。5.2 408算法大题的备考节奏与手写策略根据我个人的经验408算法大题准备得越早越好因为手写代码是需要肌肉记忆的。建议在暑假结束前把数据结构中线性表、树、图这几章的经典算法题都过一遍手写。不要用编译器检测就用纸笔写写完之后对照答案逐行检查。第一次写可能错误百出这太正常了真正的收获在于检查的过程你能亲眼看到自己在哪个边界条件上翻车。后期冲刺阶段每周抽出两到三次每次拿一道真题算法题做全真模拟。给自己限定时间15到20分钟。时间到了不管写没写完都停笔然后严格按照“思路、步骤、代码”三个维度给自己打分。这样训练两三个月考场上遇到算法题的时候你会形成一种条件反射先想最优解再快速写代码不会像第一次做2009年真题那样手忙脚乱。最后再分享一个小技巧。408不只是数据结构还有计算机组成原理、操作系统、计算机网络三座大山算法题只是数据结构这一门课里的一道综合题。如果复习时间特别紧张可以把双指针、递归、链表操作、二叉树遍历这几类高频考点优先练熟它们出现的概率最高性价比也最高。2009年这道题就是最好的起点把它彻底搞懂你收获的不只是这一道题的分数而是一整套应对408算法题的方法。我在备考的时候把这道题反反复复写了很多遍每次写都有新的体会。最开始我纠结于为什么不能直接数两遍后来我理解了“尽可能高效”的真正含义再后来我练到能在纸上两分钟写完闭上眼睛都能画出指针移动的过程。这种从生疏到熟练的过程是每一个认真准备408的人都会经历的。希望这篇复盘能帮你把这段路走得稍微顺一点。