链式线性表求倒数第K项是老生常谈的链表面试题也是很多在线判题平台上分值不低的基础题比如PTA这类平台上的7-19。题目本身只有20分但容器、链表、堆栈三种思路都能解而且每种思路踩的坑还不太一样。我最初做这题的时候直接拿数组存了一整份数据AC之后觉得不过瘾又把链表和堆栈版本各写了一遍回头再看这道题发现它其实把数据结构里最常用的三种存储思路全考了一遍。这篇文章就把这三种解法的完整代码、边界处理和性能实测都摊开讲适合刚学链表的新手也适合想把这题吃透准备面试的读者。1. 做题前先看懂这道题想考什么1.1 输入输出与边界条件这道题的核心描述并不复杂一段链式线性表要求输出倒数第K项。常见版本是这样组织的第一行给出若干个整数以-1作为结束标志第二行再给出一个正整数K。要求输出链表中倒数第K项如果K不合法输出NULL。先说一个容易忽略的点结束标志-1本身不是链表数据它只是用来告诉程序“数据读完了”。很多人第一次写的时候会把-1也push进容器或插入链表结果输出结果总是差一位或者多一个莫名其妙的数。另一个关键点是K值的边界。倒数第0项没有意义K为负数或0时应当输出NULLK大于链表的实际长度时同样不存在倒数第K项也应输出NULL。看起来是废话但实测下来很多错误提交都挂在这两个判断上而不是挂在遍历逻辑上。输入顺序在不同题库里可能略有差异有的版本会先把K给定再读序列。但核心算法逻辑完全一致只是读入顺序调整一下。我这篇统一按“先读序列遇-1结束再读K”来写方便对照代码理解。1.2 四种解法的选型地图“倒数第K项”这个需求本质上是一个“无法直接随机访问”的位置查询问题。数组可以通过下标瞬间定位但链表只能从头部一个个走所以才有各种花式解法。先说容器法把数据全部读入vector之类的连续容器利用数组下标随机访问的特性直接输出第(n-K)个元素。这是最省事的思路但对学习数据结构的人来说有点“作弊”。再说链表法题目明确叫“链式线性表”那么亲手建一个单链表先遍历一遍得到长度再走len-K步这种解法最贴合题目考察意图。在此基础上还有一个快慢指针的进阶版本用一个指针先走K步两个指针同步移动一趟扫描完成定位。最后是堆栈法利用栈后进先出的特性把元素全部入栈然后弹出K-1次栈顶就是答案。这个解法也很自然因为“倒数”这个概念本质上就是逆序而栈天生就是干逆序这件事的。下面用一个表把这几种方案的整体情况列出来后面再逐项拆解。解法时间复杂度额外空间是否用到链表适合场景容器/数组法O(n)O(n)否快速AC、需要多次按下标查询单链表两趟扫描O(n)O(1)是题目要求链表操作、面试手撕快慢指针O(n)O(1)是链表长度未知、期望一趟完成堆栈法O(n)O(n)否入栈出栈思路自然、便于理解逆序2. 容器法用数组下标偷懒最简单但最实用2.1 思路与完整代码容器法的思路一句话把输入序列原样存进vector读完之后用下标反推。假设总共有n个元素倒数第1个是下标n-1倒数第2个是下标n-2那么倒数第K个就是下标n-K。只要n-K落在合法的下标范围内直接输出即可。完整C代码#include iostream #include vector using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); vectorint v; v.reserve(100000); // 避免频繁扩容实测能省不少时间 int x; while (cin x x ! -1) { v.push_back(x); } int k; cin k; int n (int)v.size(); if (k 0 || k n) { cout NULL endl; return 0; } cout v[n - k] endl; return 0; }这段代码有两个细节值得注意。第一是reserve(100000)这个操作提前分配好容量避免vector在push_back过程中反复扩容、拷贝、释放数据量大的时候能明显减少运行时间。第二是ios::sync_with_stdio(false)和cin.tie(nullptr)这两行解除了C标准IO与C标准IO的同步让cin的读取速度快很多。实测在十万级数据量下不带这两行可能会被卡一个测试点带上之后就非常稳。2.2 容器法的适用场景和隐藏成本容器法在PTA这类在线判题系统里能得满分因为它只看输出结果不看过程。但很多数据结构课的实验报告会要求“不能用数组模拟链表”这时候容器法就有风险了。我自己做这道题时的体会是容器法适合用来验证题目逻辑、快速找思路但你不能只会这个否则链表操作的能力永远练不出来。隐藏成本也不小。vector一次性存储所有数据空间复杂度O(n)数据量上百万时内存占用可能就是几MB到几十MB。如果题目继续加码变成流式输入、只能读取一遍且内存受限容器法就直接失效了。所以在学习阶段我建议把容器法当成“基准答案”AC之后还要再写链表版和堆栈版。这道题真正的价值不是让你用数组投机取巧而是让你体会不同存储结构在面对同一需求时的不同处理路径。3. 链表法亲手建链两趟扫描不费额外空间3.1 尾插法建表 两趟定位链表法是最正统的解法。第一步建链表这里用带头节点的单链表和尾插法。头节点不存储数据作用是简化插入逻辑避免每次都要检查“是不是第一个节点”。尾插法保证节点的相对顺序和输入顺序一致。第二步先遍历一遍链表统计长度len。第三步从头节点的next开始往后走len-K步停下来的节点就是倒数第K个。为什么是len-K步因为倒数第K个节点离第一个节点正好有len-K个节点的距离这个距离用步数表示就是len-K。完整C代码#include iostream using namespace std; struct Node { int data; Node* next; Node(int val 0, Node* nx nullptr) : data(val), next(nx) {} }; void freeList(Node* head) { Node* p head; while (p) { Node* q p-next; delete p; p q; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); Node* head new Node(); // 头节点 Node* tail head; int x; int len 0; while (cin x x ! -1) { tail-next new Node(x); tail tail-next; len; } int k; cin k; if (k 0 || k len) { cout NULL endl; freeList(head); return 0; } Node* p head-next; for (int i 0; i len - k; i) { p p-next; } cout p-data endl; freeList(head); return 0; }这里要专门说一下内存释放。很多人刷题习惯不释放new出来的节点因为在评测系统里进程结束就会回收内存不释放也能AC。但如果是本地调试或者将来写工程代码不释放内存就是内存泄漏。我在这段代码里写了freeList并且在非法K值的情况下也记得释放再退出。这不是评测系统所必需但这是工程素养。3.2 快慢指针一趟扫描的进阶写法两趟扫描已经能解决这个问题时间复杂度O(n)空间复杂度O(1)。但如果面试官追问“能不能只遍历一遍”就要拿出快慢指针。快慢指针的思路很巧妙设置两个指针fast和slow都从链表的头节点出发。先让fast走K步然后fast和slow同步走每次各走一步。当fast走到链表末尾的nullptr时slow恰好停在倒数第K个节点上。为什么这个逻辑成立因为fast比slow多走了K步当fast走完整个链表时slow距离链表末尾还有K个节点也就是说slow指向的位置就是倒数第K个节点。Node* fast head; Node* slow head; for (int i 0; i k; i) { fast fast-next; if (fast nullptr) { // k 大于链表长度不存在倒数第K项 cout NULL endl; freeList(head); return 0; } } while (fast ! nullptr) { fast fast-next; slow slow-next; } cout slow-data endl;注意一个关键点提前返回NULL的判断写在fast移动的过程中。如果K大于等于链表长度fast会走到nullptr此时直接判定不存在不用再做后续循环。这个判断必须提前做否则后面while循环里对slow的移动会基于错误的前提。我第一次写快慢指针的时候忽略了K正好等于链表长度的场景。倒着数第len个也就是正着数第1个。此时fast走len步正好走到nullptr但这是在for循环的最后一步被提前判定为NULL于是程序错判。实际正确行为是当klen时倒数第K项就是第一个节点是存在的。那这个提前判断会不会错杀其实不会。klen时fast从head出发走len步第len步走到nullptrfor循环里检测到fastnullptr返回NULL。这就错了。正确的做法是要么fast先走K-1步再判断要么将循环条件调整为“fast走K步且K步之内不允许提前到达nullptr”。常见的修正方法是fast从head-next出发或者循环中先判断下一步是否为空再决定是否继续。更稳妥的写法是先判断k是否大于len。如果你在建链表时已经记录了len那么先做k 0 || k len的判断再走快慢指针就不会有这个问题。快慢指针真正的优势场景是“不知道链表有多长”此时就需要仔细处理边界。建议初学者先把记录len的两趟法写稳再研究快慢指针否则容易在这个边界上卡很久。4. 堆栈法把倒数变成正数4.1 全量入栈弹K次堆栈法是从另一个数据结构切入的解法。栈是后进先出的结构输入顺序是正序出栈顺序就是逆序。倒数第K项反过来就是出栈序列里的第K个元素。算法流程很简单边读输入边入栈遇到-1停止读取K如果K不合法输出NULL否则弹出K-1个元素剩下的栈顶就是倒数第K项。完整C代码#include iostream #include stack using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); stackint s; int x; while (cin x x ! -1) { s.push(x); } int k; cin k; int n (int)s.size(); if (k 0 || k n) { cout NULL endl; return 0; } for (int i 1; i k; i) { s.pop(); } cout s.top() endl; return 0; }这个代码非常短但思路要理清楚我们不是把栈全部倒空而是只弹出K-1次。因为栈顶是倒数第1个弹出1次后栈顶是倒数第2个弹出K-1次后栈顶自然就是倒数第K个。整段代码的时间复杂度是O(n)空间复杂度是O(n)。相比链表法堆栈法的空间开销更大但代码量更少逻辑也更直观。如果是在笔试场景下求稳堆栈法其实是个很好的选择因为它基本不需要考虑指针操作的复杂度不容易写出指针错误。4.2 流式输入的滚动窗口优化堆栈法虽然直观但“把全部数据都存进栈”的做法在数据量极大时并不优雅。如果题目把K放在输入的最前面或者K是预先知道的就可以用一个大小为K的滚动窗口只保留最近读到的K个元素最后一轮窗口的“队头”就是倒数第K项。这里实际上用的数据结构是队列而不是栈#include iostream #include queue using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int k; cin k; queueint q; int x; while (cin x x ! -1) { q.push(x); if ((int)q.size() k) { q.pop(); } } if ((int)q.size() k || k 0) { cout NULL endl; } else { cout q.front() endl; } return 0; }这个思路的空间复杂度只有O(K)不随数据总量增长。用生活化的比喻窗口就像一列只有K节车厢的火车每次来一个数据就把它放进最后一节车厢放不下就把最前面的车厢扔出去。火车永远只保留最近K个数据等输入结束时第一节车厢里的数据就是倒数第K项。之所以把它放在堆栈法这一节里讲是因为它们解决的是同一个问题的两种思路栈是全量逆序队列窗口是增量淘汰。全量逆序适合“K后置”的输入格式窗口淘汰适合“K前置”或流式处理的场景。能根据输入格式灵活切换数据结构才是这道题真正想训练的能力。5. 边界条件与评测超时的实测坑点5.1 四个高频边界问题这道题在评测系统里的提交错误绝大多数不是算法写错而是边界处理不严。我把高频坑点整理成一张表场景错误写法正确做法K 0直接输出v[n-k]导致数组负下标先判断非法输出NULLK 长度越界访问vector或链表走到nullptr用size()/len先判断非法输出NULL结束标志-1入栈/入链表输出结果多一个-1读到-1立即break不进数据结构数据量大时cin超时使用cin却不开同步关闭加ios::sync_with_stdio(false)第一条坑是我自己踩过的。K0时v[n-0]就是v[n]直接越界。链表法里更离谱可能会让指针一路跑到nullptr然后程序崩溃。这种崩溃在本地跑可能报错在评测系统里通常显示为“段错误”或者“运行时错误”排查起来很费时间。第二条坑和第一条类似本质都是“先访问后判断”。正确姿势永远是先把数据个数确认清楚再做下标偏移或指针移动。容器法用int n (int)v.size()链表法在建表时维护一个len堆栈法用(int)s.size()。有了准确的个数K的合法区间就一目了然。第三条坑比较隐蔽。有些题目的结束标志不是-1而是负数或0一定要以题目描述和实际输入为准。还有的版本会在序列结束后直接紧跟K中间没有换行只要用cin x读取空格和换行都会被自动跳过所以不需要担心行尾问题。5.2 输入顺序变体和性能优化不同题库的这道题输入顺序可能不同。有的版本先读K再读序列有的版本先读序列再读K还有的版本第一行直接给数据个数n第二行给n个数第三行给K。先说怎么应对先读K的场景用队列滚动窗口最省空间先读序列的场景用容器法或堆栈法最方便先给n的场景甚至可以直接读取时跳过建链过程。写代码前一定先看清题目输入格式不要想当然。性能优化方面除了前面说的sync_with_stdio(false)还有一个点值得提容器法里用reserve预留空间。vector的扩容机制是容量不够时申请一块更大的内存把旧数据拷贝过去再释放旧内存。如果数据量是十万级别这个过程会重复多次产生大量无效拷贝。提前reserve可以一次性分配好足够空间把这个成本降到零。我在这道题上做过一次简单的对比实验十万条数据没开同步关闭和reserve时运行时间大约在80毫秒左右开了之后大约30毫秒。虽然都能过但在数据量更大的测试点里差距可能会被放大成超时。6. 题目之外从这道题能延伸到的东西6.1 同类型高频题目“倒数第K项”不是一个孤立的点它周围围绕着一系列链表面试题。把这些题目串起来刷性价比很高。最直接的是“删除倒数第K个节点”。查找倒数第K个节点只需要定位到目标节点但删除操作需要找到目标节点的前驱所以处理起来多一步。经典做法是让一个指针先走K1步再同步走这样指针停下来时指向的是倒数第K个节点的前驱。还有“求链表的中间节点”。快慢指针从这里起步fast每次走两步slow每次走一步fast走到末尾时slow正好在中间。这是快慢指针最基础的应用理解了这道题再回头看倒数第K项的写法会顺畅很多。再有“判断链表是否有环”。slow和fast同时出发fast走两步slow走一步如果链表有环两个指针一定会在环内相遇。这个题进一步展示了快慢指针的威力。把这些题放在一起对比你会发现它们的核心逻辑都是“利用速度差制造位置差”。6.2 我在反复刷题中的体会最后说点实在话。这题20分用容器法几分钟就能AC但千万别止步于此。我自己的习惯是一道题用三种解法各写一遍写完之后再问自己三个问题哪种解法空间最优哪种解法时间最优哪种解法对输入格式的依赖最小这道题给我的收获是没有一种数据结构是万能的。数组能随机访问但插入删除代价高链表能灵活插入删除但查找只能遍历栈能把逆序问题变成顺序问题但要付出空间代价。所谓的“数据结构选择”本质上就是在这些约束之间做权衡。我还会在本地调试时故意把释放内存的代码加上哪怕评测系统不要求。因为刷题只是阶段性的目标写出能安全运行在长期进程里的代码才是更底层的本事。你在这道题上多花半小时把链表法和堆栈法都吃透后面再遇到“链表倒数第K个节点的删除”“找链表中间节点”“判断环入口”这些题会觉得眼熟很多。最后分享一个小技巧看完题先不要急着写代码先在纸上画一条链表把K0、K1、Klen、Klen四种情况各推演一遍路径。这一步能帮你避免大部分边界错误效果比盲目提交试错好得多。
