1. 这道20分题到底在考什么：不止"倒数"这么简单

链式线性表求倒数第K项，几乎是每个学数据结构的人都会撞上的题目，某OJ平台的7-19就是其中一道20分题。表面看，它考的就是"遍历链表+倒数定位"，但如果你只在纸上画个链表、心里默念"先数长度再走一遍"就交上去，大概率会踩中几个隐藏的坑。

先说清楚题目到底让你做什么：输入一串非负整数，以某个负整数作为链表数据的结束标记，紧接着再输入一个整数K，要求输出这条链表倒数第K项的值，如果取不到，就输出"NULL"。这里有个典型的误区——很多同学以为必须先自己构造出完整的链式结构，老老实实用指针去模拟一个单链表，然后再实现"倒数第K项"的逻辑。

但注意标题里给了三个提示词：容器、链表、堆栈。这说明出题人并不限定你只能用指针模拟链表，它更关注的是抽象能力。你完全可以用容器（比如vector或数组）存下数据，也可以用栈把数据反向压出来，甚至可以构造一个真正的单链表再用双指针完成。三种解法都能拿满分，只是背后的思考路径完全不同。

这道题真正的考察点也在这里：第一，你能否准确地建模出"链式线性表"的逻辑特性；第二，你能否用合适的工具在时间复杂度和空间复杂度之间做取舍；第三，你能否把所有边界情况都处理干净。K恰好等于链表长度、K大于链表长度、K等于0、链表为空——每一种情况在判题系统里都可能是一组专门构造的测试用例。所以这篇文章我打算把三种主流解法都拆开讲一遍，从原理到代码，再到互相比较，最后把边界和调试经验也聊透，争取让你一次把这道题吃干净。

2. 解法一：容器方案——用vector给节点编号，最快的AC路径

2.1 核心思路与完整代码

容器法是我在OJ上最推荐的抢分写法。思路特别直白：读数据时把每个元素原样push到vector里，等K也读完之后，倒数第K项就是数组里的第 size-K 个元素，下标为 size-K。

别小看这个思路，它的正确性建立在"数组顺序与链表顺序一致"这一前提上。既然我的目标只是拿到倒数第K个值，那我根本不需要关心节点的next指针指向哪，只需要保证"顺序"不变就行。vector天然保存了顺序，存取又是O(1)，比老老实实构造链表再遍历两次要省事得多。

#include <cstdio> #include <vector> int main() { std::vector<int> arr; int x; while (scanf("%d", &x) == 1 && x >= 0) { arr.push_back(x); } int k; scanf("%d", &k); if (k <= 0 || k > (int)arr.size()) { printf("NULL\n"); return 0; } printf("%d\n", arr[arr.size() - k]); return 0; }

不少同学第一次写会习惯用while (cin >> x && x >= 0)，这也能过，但要注意判断一次只能读一个数，别把结束标记和K一起吃掉。上面这份代码已经把结束标记排除在数据之外了，当读到的x是负整数时，它不会被push进vector，循环也随之终止。紧接着读到的整数就是K，整体逻辑很干净。

2.2 为什么容器法在OJ上最"划算"

从工程角度说，vector方案的空间复杂度是O(n)，时间复杂度是O(n)，本质上是拿空间换实现速度。但判题系统通常不care小规模的空间占用，测试数据一般也就几百到几千个节点，完全在可接受范围内。

更重要的是它的容错率。手写链表最容易出三类问题：节点没初始化、尾指针没更新、循环条件写错导致段错误。而vector几乎把所有内存管理问题都屏蔽掉了，你只需要关心下标运算。很多同学在OJ上遇到"段错误"后排查半天，其实就是链表节点连接时某个指针没有处理好。用容器方案，这种低级错误从源头就消失了。

但容器方案也有它不够"高级"的地方：空间复杂度线性。如果题目追加一个要求——只能用O(1)额外空间，那vector思路就直接失效。这也是为什么我虽然推荐它作为AC首选，但下面两种解法仍然值得好好掌握：它们分别代表了"借助栈特性解决问题"和"容器法在空间受限时的替代方案"。

3. 解法二：堆栈方案——后进先出天然适配倒数

3.1 栈解法的代码与原理

"倒数第K项"换个角度看，就是从链表的尾部往回数K个节点。而栈这种数据结构最擅长的就是"倒着看"——你把所有数据依次压栈，再弹出K次，最后一次弹出的就是倒数第K项。整个过程不需要记录链表长度，也不需要下标运算，逻辑上甚至比容器法更贴合"倒数"这个语义。

#include <cstdio> #include <stack> int main() { std::stack<int> st; int x; while (scanf("%d", &x) == 1 && x >= 0) { st.push(x); } int k; scanf("%d", &k); if (k <= 0 || k > (int)st.size()) { printf("NULL\n"); return 0; } while (--k) { st.pop(); } printf("%d\n", st.top()); return 0; }

这里有个细节值得留意：while (--k)会先自减再判断，所以当k=2时，循环只执行一次pop，栈顶元素就是倒数第2项。这个写法比while (k--)少pop一次，不用额外手动调整。我见过不少同学在这个循环条件上写错过，稍微不留神就多弹了一个元素。

3.2 栈解法的内存特征与适用场景

栈方案的时间复杂度同样是O(n)，空间复杂度也还是O(n)，因为你需要用额外的栈容器保存所有数据。从这个角度看，它和vector方案本质上是同一级别的开销，只是换了一种"顺序反转"的手段。

那栈方案的优势在哪里？它更适合"数据源本身是流式的、无法预知长度"的场景。比如数据不是一次性给全，而是一个个从网络接口或文件流里读入，你不知道总共有多少项。vector在扩容时会频繁拷贝数据，而栈的push操作在内存管理上更自然。当然在OJ上两者的实测性能差距几乎可以忽略，选哪个纯粹看个人习惯。

但我不建议你在面试或考试中只提容器法和栈法各一句就完事。面试官大概率会追问："能不能把空间复杂度压到O(1)？"这时候如果你能说出第三种解法——双指针——才是真正的加分点。接下来就聊它。

4. 解法三：双指针方案——单次遍历的最优解

4.1 快慢指针的运作原理

双指针解法，也叫快慢指针法，是这道题在"空间复杂度O(1)"约束下的标准答案。思路相当巧妙：先让快指针从头节点出发先走K步，然后慢指针从头节点出发，两指针同步前进。当快指针走到链表末尾的NULL时，慢指针恰好停在倒数第K个节点上。

为什么成立？因为快指针比慢指针始终领先K个身位。快指针到达NULL时，它走过的总长度是L，那么慢指针走过的长度就是L-K，这个位置正好是倒数第K项所在的下标。整个过程只遍历了一次链表，没有额外开辟线性空间，是三种解法里"最优雅"的。

但如果题目不给一个已经构造好的链表，你需要先自己建链表，再用双指针处理，代码量比前两种明显大。这也是它作为"面试向"解法的特性——在OJ抢分时不一定划算，但在考察你链表基本功时很有价值。

4.2 手工构造单链表并完成倒数查找的完整实现

#include <cstdio> #include <cstdlib> struct Node { int data; Node* next; }; int main() { Node* head = NULL; Node* tail = NULL; int x; while (scanf("%d", &x) == 1 && x >= 0) { Node* node = (Node*)malloc(sizeof(Node)); node->data = x; node->next = NULL; if (head == NULL) { head = node; } else { tail->next = node; } tail = node; } int k; scanf("%d", &k); if (k <= 0) { printf("NULL\n"); return 0; } Node* fast = head; Node* slow = head; int steps = 0; while (fast != NULL && steps < k) { fast = fast->next; steps++; } if (steps < k) { printf("NULL\n"); return 0; } while (fast != NULL) { fast = fast->next; slow = slow->next; } printf("%d\n", slow->data); return 0; }

注意代码里的细节：首先处理K<=0的情况，防止先走K步时出现非法操作；其次在让快指针先走K步时，用一个steps变量记录实际走过的步数。如果链表长度小于K，那么快指针在走完之前就会碰到NULL，此时steps < k，直接输出NULL。这个判断非常重要，少了它，后面printf("%d\n", slow->data)会对空指针解引用，导致段错误。

还有一个容易忽略的细节：如果K恰好等于链表长度，那么快指针走完K步之后正好停在NULL上。此时进入第二个while循环的条件fast != NULL不成立，循环一次都不执行，慢指针仍然停在头节点。头节点就是倒数第K项吗？是的，倒数第L项就是首元节点，这个逻辑是自洽的。所以不需要为"K等于链长"单独加分支。

当链表为空且K>0时，上面的while循环在第一步就因为fast == NULL退出，steps还是0，steps < k成立，同样会输出NULL，不会访问空指针。

如果链表为空且K=0，则会先被k <= 0拦截，输出NULL。这样四种异常场景（空链表+K>0、空链表+K=0、非空+K>链长、K<=0）都被覆盖了。

5. 边界条件与隐藏扣分点：K值异常时的完整处理清单

5.1 完整边界清单与预期行为

很多同学这道题拿不到满分，不是因为主逻辑写不出来，而是边界处理不到位。我把自己踩过的、以及帮别人排查过的边界情况汇总成一张表，你写代码前对着过一遍，基本就能保证提交后不再被边界用例打回。

注意K等于链表长度和K大于链表长度这两种情况非常容易被混为一谈。K等于链长是合法的，要输出头节点的值；K大于链长才是非法的，要输出NULL。区别就在于让快指针先走K步时，快指针是否能在不越界的情况下走完K步。能走完则合法，走不完则非法。

5.2 边界处理的"20分"意义

OJ判题通常会把测试点拆开，一个测试点对应一组特殊输入。边界用例绝对不只是附加题——很多同学主逻辑对了，却因为漏了K=0或K大于链表长度直接被扣掉4到6分。20分的题，因为一个小分支丢掉5分，可能直接让你的总排名掉一个档次。

双指针版本中的steps < k判断尤其重要。假如你已经知道链表长度TeLength，你也可以先算出len然后判断k > len，但题目输入没有给你链表长度，你必须边构建边计数。最稳妥的做法是：构建链表时用一个变量cnt记录节点总数，然后判断k > cnt。这和steps < k是等价的，但显式记录长度更容易读、更容易防止低级错误。

我推荐在代码里同时做两层防护：第一层是k <= 0，第二层是构建完链表后用节点总数和K比较。如果你用的是容器方案，那k > arr.size()就是唯一的长度判断；如果用了栈方案，那就是k > st.size()。总之，K值的各种异常组合必须在输出前被全部拦截住，绝不能让它带着非法值进入指针运算或下标运算。

6. 复杂度账本与选型思路：判题、面试、工程场景怎么选

6.1 三种解法的复杂度对比

三种解法的正确性都没问题，它们之间的差异集中在空间开销、代码量、以及你对数据结构特性的理解深度上。下面这张表可以作为选型参考：

容器法和堆栈法在复杂度上完全一致，差异只是抽象工具不同。双指针法在空间上胜出，但代价是需要维护一个真正的手工链表，并且要考虑空指针解引用的问题。从纯算法角度看，双指针法是最优解。

但在OJ上，我会毫不犹豫选择容器法或堆栈法。原因很实在：OJ只关心你的答案对不对、跑得快不快，不关心你用了多少额外内存。测试数据规模通常只有几百到几千个节点，多开一个vector或stack根本不会触发内存限制。既然代码越短、越不容易出bug，就越值得优先选。

6.2 从面试官视角看这道题

面试官如果问这道题，意图往往也在第三层。他先看你能否用容器法快速给出正确解，这是考察基础实现能力；然后追问"能不能不用额外存储空间"，这是考察你对链表结构的理解和对双指针技巧的掌握；如果再用"如果这是一个只知道头节点的单向链表"来强调一遍，那就是看你会不会做那个O(1)空间的优化。

我在模拟面试时见过不少候选人卡在最后一步。思路是懂的，说"两个指针差K步"，但一写代码就忘记处理K大于链长的情况，或者让慢指针在快指针还没走完K步时就提前进入第二步循环。所以你自己练习时，建议三种写法都各实现一遍，特别是双指针版本要反复跑边界用例，形成肌肉记忆。

工程场景里，双指针思路也更常用。比如日志系统里统计倒数第K条记录、分页场景下定位倒数第K页的偏移，这类问题往往不希望你一次性把所有数据加载到内存。维护一个头部指针和一个滞后K位的指针，在数据流上边读边处理，才是更可持续的做法。

7. 提测自查与易错点复盘：从编译错误到段错误

7.1 常见错误清单

哪怕思路完全正确，提交时也可能被各种实现细节绊倒。我把容易出现的问题列在这里，每一条都是我或周围同学真实踩过的坑：

• 误把结束标记当成数据：结束标记是负整数，应该只用来终止循环，不能被push进容器或压入栈。如果读入逻辑写成了do...while，很容易多存一个结束标记。
• K读取时机不对：K必须在所有链表数据读完之后再读，不能放在循环里。要是把K也当作链表数据的一部分，结果会变成找倒数第K个负整数的位置，完全偏离题意。
• 忘了K<=0的情况：双指针版本里，如果K<=0，fast先走的循环条件无法处理，这属于非法输入，必须单独拦截。
• 空链表下的空指针解引用：输出NULL前，千万别访问任何指针。特别是双指针版本，如果链表为空，slow->data会直接触发段错误。
• 在循环里移动tail时没考虑头节点：构建链表时，第一个节点要赋值给head，后续节点才接到tail->next后面。漏掉第一个节点的特殊情况，会导致链表开头多一个未被正确链接的节点。

7.2 自测用例设计

提交之前，我建议你至少跑一遍下面这几组输入，确认输出和预期一致：

输入: 1 2 3 4 5 -1 2 输出: 4 输入: 1 2 3 4 5 -1 5 输出: 1 输入: 1 2 3 4 5 -1 6 输出: NULL 输入: 1 -1 1 输出: 1 输入: -1 1 输出: NULL 输入: 5 -1 0 输出: NULL

这六组覆盖了正常情况、K等于链长、K大于链长、单节点链表、空链表、K为0的非法值。视频演示可能看着直观，但自己动手跑到输出全部正确后再提交，才是稳妥的做法。

还有一种自查思路是构造"中间位置"的大规模数据，验证双指针移动过程中没有丢失节点。比如生成一万个连续整数，K取5000，输出应该是第5001个整数，也就是5000。这类随机大样例可以帮你排除构建链表时指针错位的偶发问题。

最后说一句个人习惯：我在OJ上提交这道题时会优先用容器法，AC之后再专门用双指针法写一遍作为练习。两种方式都跑通，才算真正把这20分吃透了。毕竟考试和面试不会只考你一次"倒数第K项"，它背后的链表操作、边界思维、空间换时间判断题，才是任何时候都通用的东西。