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

如果你准备过408考研，2009年那道算法大题应该是绕不开的。它几乎是每一本408真题资料里都会第一个开讲的链表题，也是很多人第一次真正意识到“算法题不是背代码”这个道理的地方。这篇文章就来完整复盘这道题，把考点定位、思路推导、标准代码、常见错误以及它对后续复习的价值一次讲清楚。

当年这道题之所以被反复提起，首先因为2009年是408计算机学科专业基础综合统考的第一年，命题组还在摸索风格，题目普遍偏基础，却已经把“数据结构算法设计题”的基本套路亮了出来：给定一个经典结构，要求设计一个时间上尽可能高效的算法，并完成从思想、步骤到代码的全过程书写。这一套要求，后来成了408每年最后那道算法综合题的固定模板。对于现在刷题备考的同学来说，吃透这一道题，等于提前熟悉了考研算法大题的整个游戏规则。

1. 2009年408算法题到底考了什么

1.1 原题还原与当年考场上的真实处境

为了避免大家去翻旧书，我把这道题的题干完整还原在这里：

已知一个带有表头结点的单链表，结点结构为data、link，假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第 k 个位置上的结点（k 为正整数）。若查找成功，算法输出该结点的data域的值，并返回 1；否则，只返回 0。要求：

1. 描述算法的基本设计思想；
2. 描述算法的详细实现步骤；
3. 根据设计思想和实现步骤，采用 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 步后到达第 k+1 个结点，慢指针还在第 1 个结点，两个指针之间正好隔了 k 个结点。之后两个指针同步移动，距离始终保持不变。当快指针到达 NULL 时，慢指针就在倒数第 k 个结点上。

2.3 边界条件与正确性证明

要写出正确的代码，光知道思路还不够，必须把边界条件想清楚。这里我用一个简单的代数推导来说明解法为什么成立。

假设链表长度为 n（数据结点个数）。快指针 q 先走 k 步，分两种情况。第一种，如果 q 在走完 k 步之前就遇到了 NULL，说明 k 大于 n，链表中根本不存在倒数第 k 个结点，此时直接返回 0。第二种，如果 q 成功走完 k 步，此时 q 指向第 k+1 个结点，慢指针 p 指向第 1 个结点，两者距离为 k。接下来让 p 和 q 同步走，当 q 到达 NULL 时，q 一共又走了 n-k 步。p 也从第 1 个结点移动了 n-k 步，到达第 (n-k)+1 = n-k+1 个结点。从链表末尾往前数，第 n-k+1 个结点正好是倒数第 k 个结点。

这个推导还能帮助我们写出正确的循环终止条件。有些同学喜欢让快指针先走 k-1 步，然后判断“当 q->link 为 NULL 时 p 指向倒数第 k 个结点”，这种写法也可以，但边界条件更隐蔽，容易出错。我更推荐先走 k 步、以 q 是否为 NULL 作为循环终止条件的写法，因为 NULL 的判断比 q->link 的判断更直观，也不容易在 k 的取值上犯糊涂。

边界情况至少要想清楚这几组：k 大于链表长度时返回 0；k 恰好等于链表长度时，处理结果应该是第一个数据结点；链表只有一个数据结点且 k=1 时，处理结果应该是这个结点本身；链表只有头结点没有任何数据结点时，任何正整数 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 是正整数，所以严格来说不判断 k<=0 也可以，但写上这个判断会让代码更严谨。阅卷老师看到这种细节，会认为你考虑问题比较全面。当然，如果你担心多写了反而画蛇添足，不写也不算错，毕竟题目已经限定了 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 常见错误清单

我把历年考生在这道题上最容易犯的错误整理成了一个表，你可以对照检查自己的代码有没有踩中过。

这里我想重点说两遍遍历和辅助数组这两个错误。它们的共同点是：算法本身能得出正确答案，但不是“尽可能高效”。在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的人都会经历的。希望这篇复盘能帮你把这段路走得稍微顺一点。