很多学数据结构的人第一次被链表整破防都是从这个题开始的明明逻辑很简单就是找倒数第K个结点但一放到在线判题平台边界条件马上让你现原形。这篇文章直接说清楚三类解法最朴素的两遍遍历、最推荐的双指针、以及很多人偷懒时用的容器/堆栈做法每个都给出可直接粘贴的代码顺便把K越界、头结点、输入终止这几个最容易出bug的地方一起解决。1. 题目考点与核心难点1.1 题面速读与考点拆解这类题目在在线评测平台上很常见外壳是“链式线性表”核心要求就一句话给定一个单链表找出倒数第K个结点的值。题面通常这样描述第一行给出一个正整数K第二行给出若干正整数以负数结束表示链式线性表的数据输出倒数第K项的值如果K值非法输出NULL具体输出约定以题面为准。光看题面这题确实只有20分的分量。但真正动手写之后问题马上冒出来链表怎么建负数结束符要不要进链表K大于链表长度怎么办倒数第1个是不是最后一个这题表面考链表实际同时考了三件事第一能不能熟练完成动态建链和遍历第二有没有边界条件意识第三能不能在时间和空间上做取舍。很多20分的题并不难但通过率低原因往往不是算法而是这些细节。1.2 为什么这类题容易卡住数组题里找倒数第K个元素直接下标访问就行30秒写完。链表没有随机访问能力只能从头结点一个一个往后走这就把很多“用数组思维写链表”的人拦住了。我在练习时见过不少人写出这样的循环从头结点开始数数到某个位置就输出但问他“到底走几步才能到达倒数第K个”他自己都说不清。这个题还有一层陷阱输入格式不是一次给你一个数组而是要求你用链表存储。如果建链时没有用尾插法或者结束符被存进链表后面算倒数第K项时结果就会莫名其妙差一个。我自己在本地跑得好好的一提交就错后来才发现第二行的负数被当作数据存进去了。这种和“平台输入习惯”相关的坑属于不跑几遍根本想不到的类型。另外题目标签里的“容器/堆栈”不是随便写的。对于很多初学者这是第一个意识到“不同数据结构可以解决同一个问题”的题目链表能存栈也能存vector容器也能存。怎么在考场环境下选一个最稳的方案本身就是经验。2. 三种主流解法的思路拆解2.1 两遍遍历最直觉的解法先数出链表长度再从头走到指定位置。这个思路不需要任何技巧完全依赖“第n-K1个节点就是倒数第K个”这个换算关系。如果用带头结点的链表从头结点的next开始走len-K步正好落到倒数第K个节点上。为什么要走len-K步而不是len-K1步因为初始位置已经是第一个数据节点走0步就是第1个节点走len-1步就是第len个节点。想要到达倒数第K个第len-K1个只需要走len-K步。这个解法的时间复杂度是O(n)空间复杂度O(1)。优点是逻辑绝对清晰几乎不可能写错缺点是要完整遍历两次链表。第一次循环跑完得到的长度只为了算一个步数多少有点“浪费”。但在OJ上两次遍历也是O(n)没有本质差别。2.2 快慢双指针一次遍历搞定快慢指针的思路可以这样理解想象两个人在跑道上同向跑步快的人先跑出K步然后两个人以相同速度前进。当快的人跑到终点的那一刻慢的人距离终点恰好还有K步——也就是说慢的人所在位置就是倒数第K个位置。代码里的fast指针就是那个快的人slow指针是慢的人。fast先走K步接着fast和slow一起一步一步走。当fast变成NULL时slow正好指向倒数第K个节点。整个过程只需要一个循环代码量也不大而且避免了“先统计长度再算位置”的那一步换算。注意这里的“先走K步”如果写成循环必须做边界检查。假如K大于链表长度fast在走K步的过程中就会提前变成NULL这时直接返回“不存在”即可。很多人在这一步漏掉了判断导致越界访问程序直接崩溃。2.3 容器与堆栈做法借数据结构偷懒题目标签里出现“堆栈”是有道理的。链表本身是顺序结构要找倒数第K个如果先把所有数据压进栈栈天然的后进先出特性会让“倒数”这件事变得极其直观倒数第K个就是从栈顶往下数第K个元素。如果用C语言不开一个链表栈直接拿数组模拟栈就够用。读入一个正整数就放进数组top指向最后一个空位。结束后倒数第K个元素在数组里的下标是top-K。这个下标换算非常清晰只要K不越界一次就可以取到答案。如果用C更省事的做法是直接上vector容器。vector支持随机访问把数据全部push_back之后v[v.size() - K]就是倒数第K个元素。这种写法严格来说已经不算“链表题”了因为根本没有用链表存储数据。但在很多评测平台上只要结果对就能通过这也是为什么总有人说“这题用vector秒杀”。2.4 方案对比与选型建议解法时间复杂度空间复杂度是否必须建链表适用场景两遍遍历O(n)O(1)是逻辑最直白适合新手练习快慢双指针O(n)O(1)是面试和竞赛更欣赏推荐重点掌握栈/容器O(n)O(n)否写起来最快适合快速AC或验证思路我个人的建议是考试或比赛时如果完全没思路直接用vector或数组模拟栈抢分但如果这道题出现在数据结构作业里目的显然是练链表那就老老实实用双指针写一遍。两种方案都跑通之后你才算真正理解了“为什么链表题需要指针思维”。3. 完整实现与关键代码细节3.1 带头结点的尾插法建链建链表有两个关键选择带不带头结点头插还是尾插。头插法会把输入顺序反过来这在“求倒数第K项”的题里不是不能做但会把思路绕晕属于自己给自己加戏。更稳妥的是尾插法新节点永远接在链表尾部这样链表里的数据顺序和输入顺序完全一致后续找倒数第K项时心智负担最小。带头结点的好处更大。如果不带头结点链表为空时需要单独改头指针插入第一个节点和插入后续节点的代码也要分开处理带头结点后所有新节点统一插到尾结点之后空链表和非空链表的行为完全统一。特别是判题数据里可能出现空链表带头结点能省掉大量if分支。以下是建链函数typedef struct Node { int data; struct Node *next; } Node; Node* buildList() { Node *head (Node*)malloc(sizeof(Node)); head-next NULL; Node *tail head; int x; while (scanf(%d, x) 1 x 0) { Node *p (Node*)malloc(sizeof(Node)); p-data x; p-next NULL; tail-next p; tail p; } return head; }代码里最关键的是循环条件x 0。题目要求以负数结束意味着负数本身不是有效数据所以不能进链表。如果这里写成了x ! -1一旦题面的结束符不是-1而是别的负数整个链表就会多存一个结点。3.2 快慢指针版完整实现下面是这道题最推荐的写法。定义好节点结构后求倒数第K个节点只需要一个函数#define NOT_FOUND -999999 int findKthFromEnd(Node *head, int k) { if (k 0 || head-next NULL) { return NOT_FOUND; } Node *fast head-next; Node *slow head-next; for (int i 0; i k; i) { if (fast NULL) { return NOT_FOUND; } fast fast-next; } while (fast ! NULL) { fast fast-next; slow slow-next; } return slow-data; }逐步解释这段代码k 0处理“倒数第0项”这种非法输入。虽然题目说K是正整数但多写一个判断不会有坏处。head-next NULL处理空链表。空链表没有倒数第K项直接返回不存在。fast和slow都从head-next开始也就是第一个数据节点。带头结点时最容易犯的错就是从head开始这样所有结果都会差一个位置。第一个循环让fast先走K步。如果K大于链表长度fast在走完K步之前就会遇到NULL此时直接判定K非法。第二个循环是同步移动。fast到NULL时slow停在倒数第K个节点上。这里有一个值得单独测试的边界当K恰好等于链表长度时fast走K步后正好等于NULL第二个循环一次都不执行slow仍然指向第一个节点。倒数第len个节点就是第一个节点结果正确。main函数里的调用也很简单int main() { int k; scanf(%d, k); Node *head buildList(); int ans findKthFromEnd(head, k); if (ans NOT_FOUND) { printf(NULL\n); } else { printf(%d\n, ans); } destroyList(head); return 0; }3.3 堆栈版与容器版实现用数组模拟栈是最轻量的偷懒做法。代码如下#define MAXN 100005 int main() { int stack[MAXN]; int top 0; int k, x; scanf(%d, k); while (scanf(%d, x) 1 x 0) { stack[top] x; } if (top 0 || k 0 || k top) { printf(NULL\n); } else { printf(%d\n, stack[top - k]); } return 0; }这个方案的巧妙之处在于完全不用关心“倒数”怎么换算。数据按顺序入栈后栈顶就是最后一个元素倒数第K个元素只需要从栈顶方向往回数K个位置。数组下标top - K就是答案的位置。用C的vector版本更符合“容器”标签#include iostream #include vector using namespace std; int main() { int k, x; cin k; vectorint v; while (cin x x 0) { v.push_back(x); } if (v.empty() || k 0 || k (int)v.size()) { cout NULL endl; } else { cout v[v.size() - k] endl; } return 0; }vector的随机访问能力让代码短得不像一道链表题。注意v.size()返回的是无符号类型和k比较时建议强转成int避免无符号数和有符号数比较时出现奇怪行为。另外v.empty()判断非常有必要没有它空链表时v.size() - k就是一个很大的无符号数下标直接越界。如果非要用std::stack也不是不行但取倒数第K个元素只能反复弹出stackint st; while (cin x x 0) st.push(x); if (st.empty() || k 0 || k (int)st.size()) { cout NULL endl; } else { int cnt k; int ans; while (cnt--) { ans st.top(); st.pop(); } cout ans endl; }这里最容易写错的是弹出次数。如果写成while (--k)倒数第1个元素会被跳过永远得到错误的答案。这也是为什么我更喜欢vector的下标写法少一步操作就少一个出错机会。3.4 输入读取的隐藏细节在线评测平台的输入有几个习惯和本地测试不一样第一不要依赖“一行恰好有几个数据”。题目说第二行给若干正整数但实际数据可能换行可能多个空格直接用scanf或cin循环读取它们会自动跳过空白字符。第二循环终止条件要写成两个条件的合取读取成功并且当前值不是负数。读不到数据时scanf返回EOFcin会进入失败状态这两个条件都能覆盖到。只写x 0而不检查读取是否成功可能会把上一次残留的x继续用下去造成死循环。第三K要放在建链之前读。如果建链的时候先把所有数据读完了再想读K只能重新读一遍输入显然不行。所以main函数里的顺序必须是scanf读K再buildList。输出方面也有细节。题目要求的“NULL”是四个大写字母不是“null”也不是“None”。有些平台输出空行有些输出-1具体以题面样本为准。我见过有人因为输出时多打了一个空格被判格式错误也见过有人把NULL写成了小写提交五六次才发现。4. 我踩过的坑和排查思路4.1 负数结束符被存进链表这是我在这个题上踩的第一个坑。当时我写的循环是while (scanf(%d, x) 1) { if (x 0) break; // 插入链表 }看起来没什么问题但我在另一个函数里统一用x ! -1判断结果测试数据里恰好结束符是-1通过了换一组结束符为-2的数据链表就会多存一个负数节点。从那以后我统一用x 0作为入链表条件和具体负数值解耦。题面说“以负数结束”不是“以-1结束”写 0才最稳。4.2 快慢指针的边界步数差一快慢指针的经典错误有两种fast先行k-1步或者同步循环写成while (fast-next)。第一种会让结果变成倒数第K1个节点第二种在K1时会多跳一步把倒数第1个变成倒数第0个。我自己总结的验证方法构造三个固定用例每个都用眼睛跟一遍。单节点链表K1结果应该是唯一节点本身三节点链表K3结果应该是第一个节点三节点链表K4结果应该是不存在。这三个用例全过基本能排除绝大多数步数错误。尤其是第三个能验证fast先走K步时的空指针判断是否到位。4.3 带头结点和不带头结点的混用如果一个人今天写带头结点的题目明天写不带头结点的题目最容易搞混初始化位置。带头结点时fast和slow从head-next出发不带头结点时从head出发。一旦混用结果会稳定地差一个位置。我的建议是自己在本地固定带头结点这个习惯。原因很简单许多在线评测平台的链表题模板本身就带了头结点带头结点后空链表和非空链表的处理逻辑统一心智负担小。真正上考场时先看题目模板到底给的是哪种头再决定初始化位置。4.4 栈/容器版本的下标和弹出次数数组模拟栈时如果把最后一个入栈元素的下标当成top然后访问stack[top - k 1]结果会整体偏一位。正确写法是stack[top - k]。举例入栈三个元素1、2、3top是3倒数第1个元素下标是2也就是3-1不是3-11。用std::stack弹栈时还有一种隐蔽错误先判断k和栈大小合法然后用同一个k变量反复递减最后还想输出k。此时k已经变成0了。正确的做法是复制一份用副本做循环计数。4.5 调试链表题的通用技巧链表题出错时别死盯代码写个打印函数直接看效果最有效void printList(Node *head) { for (Node *p head-next; p ! NULL; p p-next) { printf(%d , p-data); } printf(\n); }在fast走完K步后和同步循环结束后各打印一次slow-data能立刻看出来是不是步数问题。另一个建议是每道链表题都写一个destroyList释放内存。评测平台不强求你释放但本地用内存检测工具时不释放会报告泄漏。练习阶段养成习惯对以后写工程代码也有好处。5. 从这题延伸出去链表的通用题感5.1 快慢指针是一个可复用的模板求倒数第K项只是快慢指针的应用之一。同一个模板稍微变形就能解决好几类高频题找中间节点fast每次走两步slow每次走一步fast到末尾时slow正好在中间判断链表是否有环fast走两步slow走一步两者相遇说明有环删除倒数第N个节点先用快慢指针定位再修改前驱结点的next指针。这些题的共同本质是“用两个不同起点或不同速度的指针在链表中制造位置差”。理解这一点之后你看到“倒数第K个”第一反应就应该是快慢指针而不是数长度。5.2 链表基本功清单这题练完下面几个操作最好紧接着写一遍反转链表迭代法和递归法各写一次合并两个有序链表注意其中一个为空时的处理删除倒数第N个节点可以直接复用本文的双指针模板判断回文链表先找中点再反转后半段找两个链表的第一个相交节点双指针走完一个走另一个。把这些都练熟后普通数据结构考试里的链表题基本能覆盖八成。它们彼此之间的联系很强今天学的快慢指针明天就在回文链表里再用一次。5.3 容器思维与指针思维的取舍在线评测平台上用vector能AC甚至代码更短。但这不代表可以不学链表。数据结构这门课的价值恰恰在于让你理解“不同存储结构适合不同操作”。数组适合随机访问链表适合频繁插入删除栈天然支持后进先出。求倒数第K项用栈很方便但如果是让“在原链表上原地解决”栈就不满足要求。我的建议是分两步走拿到题目先用最快的方式AC建立信心然后强制自己再用链表思路写一遍。第一种写法让你知道答案长什么样第二种写法让你理解为什么链表题要这么解。两者都跑了才算真正会做这道题。个人刷题的经验是这种20分的题真正值钱的地方不在于AC那一刻的快感而在于它把“边界条件”这四个字刻进习惯。如果你能把空链表、K等于长度、K超出长度、K等于1这些情况都当成默认测试项以后遇到更复杂的链表操作心里就有底了。最后再分享一个小技巧刷完这题之后顺手把“删除倒数第N个节点”也做了。你会发现套路几乎一样但手感和信心会完全不同。链表题就是这样一个模板通了一片题就通了。
)
