1. 从一道高频面试题说起

“面试题.返回倒数第k个节点”这行标题，过去几年我见过太多次了——不管是校招还是社招，不管是后端岗还是客户端岗，这道题出现的频率高得离谱。它考察的知识点不算难，却能把一个人的基本功底子摸得清清楚楚：链表的遍历方式、边界条件的敏感度、双指针的思路、还有代码的稳定性。

这道题本身极其简单：给你一个单链表，返回倒数第 k 个节点的值。比如链表是1 -> 2 -> 3 -> 4 -> 5，k = 2，那倒数第 2 个节点就是 4。

很多同学第一次看到这题，脑子里第一反应是：“这有什么好考的？先遍历一遍数长度，再正着走 n-k 步不就完事了？”确实，这么做完全正确，时间复杂度 O(n)，空间复杂度 O(1)，没有任何问题。但为什么面试官偏爱这道题？因为它在“最优解”之上，还藏着一个更巧的思路——双指针。这个思路如果没人点破，很多人当场想不到，而想到了，就是一次展示自己思维深度的机会。

这篇文章我会把这题从题干到边界条件，从朴素解法到双指针写法，包括面试现场怎么沟通、怎么主动给出更优解、怎么写代码不容易出 bug，全部拆开讲透。后面还会顺带说几个高频变体，比如“删除倒数第 k 个节点”“求链表中点”，因为掌握了核心思路，这些变形题就是白送分。

2. 题目解读与思路拆解

2.1 原题到底在问什么

先明确题目细节。很多版本里这题会给出单链表的定义，通常是这样的结构：

struct ListNode { int val; struct ListNode *next; };

函数签名大概是：

int kthToLast(struct ListNode* head, int k);

返回的是节点的值（int），而不是节点指针，也不是要求删除节点。这里有个小坑要特别注意：题目说的是“倒数第 k 个节点”，k 是从 1 开始计数的，而不是从 0 开始。也就是说，k = 1 时返回的是链表最后一个节点的值，k = 链表长度时返回的是头节点的值。这个约定搞反了，后面全盘皆错。

题目的隐含假设是 k 合法，也就是1 <= k <= 链表长度。但实际面试时你最好主动问一句：“k 会不会大于链表的长度？如果会，我要怎么处理？”这不是多此一举，面试官会很在意这种对边界条件的敏感性。

2.2 为什么这是一个好题

这道题看似简单，但它至少踩中了三个考察点。

第一是链表的基本功。链表不是数组，没有随机访问能力，你不能直接通过下标取倒数第 k 个元素。这强迫你思考“怎么在单向链表上往前走”，而不是条件反射地套数组逻辑。

第二是边界条件。空链表怎么处理？k = 1 怎么办？k = 链表长度怎么办？k 非法怎么办？每个边界点都是一次判断你是否细心的地方。

第三是最优解思维。暴力解法可以过，但能不能想到一次遍历就拿到结果，这是区分“会写代码”和“会思考算法”的关键分界线。双指针解法不复杂，但它体现的是一种“用距离差来定位”的思想，这种思想在很多算法题里反复出现。

2.3 两条主路线：遍历计数与双指针

先说最自然的方案——两次遍历。

• 第一次遍历：从头走到尾，统计链表节点个数，记为 n。
• 第二次遍历：从头再走 n - k 步，到达的节点就是倒数第 k 个节点。

举个例子，链表总长 n = 5，k = 2，那么正数第 4 个节点就是倒数第 2 个节点，从头走 5 - 2 = 3 步就到了。这个思路简单可靠，时间复杂度 O(n)，空间复杂度 O(1)。这已经能通过所有测试用例了。

再说双指针方案——一次遍历。

• 初始化两个指针 slow 和 fast，都指向头节点。
• 先让 fast 往前走 k 步。
• 然后 slow 和 fast 一起往前走，每轮各走一步。
• 当 fast 走到链表尾部（null）时，slow 指向的就是倒数第 k 个节点。

背后的逻辑其实是一种“长度差”的物理直觉：fast 先走了 k 步，相当于在 slow 前面拉开了一个长度为 k 的窗口。当 fast 触底时，这个窗口的尾部正好卡在链表倒数第 k 个节点上。

那为什么敢保证这个窗口一直有效？因为在 fast 先走 k 步的过程中，如果链表长度不足 k，fast 会提前走到 null，这时就说明 k 非法。这恰好也成了检查 k 是否越界的天然机制。

3. 解法一：先数长度再定位

3.1 完整代码实现

这个方案写起来非常简单，几乎不会有语法层面的坑。我用 C 语言版本作为主实现，因为面试场景下 C 语言最常见，而且更能体现对指针的理解。

int kthToLast(struct ListNode* head, int k) { if (head == NULL) { // 根据题目约定处理，这里假设返回 -1 表示非法 return -1; } int len = 0; struct ListNode* p = head; while (p != NULL) { len++; p = p->next; } // 如果 k 不在合法范围内，按约定处理 if (k <= 0 || k > len) { return -1; } int steps = len - k; p = head; while (steps > 0) { p = p->next; steps--; } return p->val; }

这段代码的关键点有三个：空链表判断、k 合法范围判断、第二次遍历的步数计算。每一步都很直白，没有任何绕弯的地方。

3.2 时间复杂度与空间复杂度分析

两次遍历，但每次都是完整的 O(n) 量级，所以总的时间复杂度是 O(n)。严格来说，第一次遍历花了 n 步，第二次最多 n 步，加起来是 2n 步，但常数项在复杂度分析里是被忽略的，因此仍然是 O(n)。

空间上只用了两个指针变量，没有额外分配与链表规模相关的内存，所以空间复杂度是 O(1)。

这个解法的优点是逻辑清晰、不容易出错，特别适合在面试一开始、还没有深入思考时就先写出一个“保底版本”。缺点也很明显：链表要遍历两遍。对于单链表这种只能顺序访问的结构，两遍遍历在一些极端场景下会是性能短板——比如链表数据在磁盘上、或者链表节点数量巨大的流式场景，两遍遍历的代价可能是实实在在的。

3.3 这个解法的两个隐藏问题

第一个隐藏问题是：如果你拿到的头节点是空的，这个解法能不能优雅处理？能，但前提是你必须事先想清楚返回值约定。很多面试者在代码里直接return -1，如果面试官追问“节点的 val 可能本身就是 -1 怎么办”，就会有点尴尬。所以更稳的做法是：先跟面试官对齐约定，或者用一个独立的错误标志，比如bool* error来传出错误信息。

第二个问题是：第二次遍历时用while (steps > 0)这个写法，比for (int i = 0; i < steps; i++)更不容易因为步数计算错误而出 bug。因为len - k这个值如果算错，问题通常出在读题不仔细——比如把 k 当成从 0 开始计数，那len - k就会多走一步，直接取到倒数第 k+1 个节点。这个细节我会在后面的常见问题里再展开。

4. 解法二：双指针一次遍历（面试官真正想看的）

4.1 核心思路详解

双指针解法的核心就一句话：让一个指针先走 k 步，然后两个指针同步前进，快的走到头时，慢的正好在倒数第 k 个位置。

很多同学第一次看到这个解法时，会觉得“这不就是数学技巧吗？有什么了不起的？”但仔细想想，它其实是一种非常通用的思想——通过两个指针之间的相对距离来定位位置。这个思想在“判断链表是否有环”（快慢指针速度差为 2）、“寻找链表中点”（速度差为 1）等题目里都会用到。也就是说，学会这一题，等于打通了双指针类题目的任督二脉。

为什么快指针先走 k 步，而不是 k-1 步？这取决于你对“倒数第 k 个”的定义。我在前面强调过，k 从 1 开始计数。你要保证的是：当 fast 到达 null 时，slow 指向倒数第 k 个节点。如果 fast 先走 k 步，那么当 fast 再走完剩余的 n-k 步时，slow 也同步走了 n-k 步。slow 从第 1 个节点开始走了 n-k 步之后，停在第 n-k+1 个节点，这就是倒数第 k 个。数学关系严丝合缝。

如果这里你忘了 k 的计数约定，改成 fast 先走 k-1 步，那得到的结果就是倒数第 k+1 个节点。这是一个特别容易犯的错，面试时一定要先确认清楚。

4.2 完整代码实现

int kthToLast(struct ListNode* head, int k) { if (head == NULL || k <= 0) { return -1; } struct ListNode* fast = head; struct ListNode* slow = head; // 第一步：fast 先走 k 步 for (int i = 0; i < k; i++) { if (fast == NULL) { // 链表长度小于 k，说明 k 非法 return -1; } fast = fast->next; } // 第二步：fast 和 slow 同步前进 while (fast != NULL) { slow = slow->next; fast = fast->next; } return slow->val; }

这段代码只遍历了一次链表，每一步操作都是常数时间，总耗时恰好是 n 次指针移动，时间复杂度 O(n)，比两次遍历的版本少了一半的常数。空间复杂度仍然是 O(1)。

4.3 为什么双指针解法更优秀

从复杂度上看，O(n) 和 O(2n) 在渐进意义上没有区别，但实际工程和面试评价中，一次遍历往往更能体现代码的“优雅程度”。

更重要的是双指针解法自带 k 合法性检查机制。在两次遍历的版本里，你需要先数完整个链表才知道 k 是否越界；而在双指针解法里，fast 先走 k 步的过程中如果撞上了 null，立刻就能判断 k 非法，不需要额外扫描一遍。虽然渐进复杂度没有改变，但在处理“超大链表 + 非法 k”的场景下，双指针确实能更快地报错。

还有一个不能忽视的点是：双指针解法在“流式数据”或“无法二次遍历的数据结构”下依然成立。比如你拿到的是一个只能单向遍历一次的迭代器，或者数据源不支持回溯，这时两次遍历的方案直接失效，但双指针依然能算出倒数第 k 个元素。这个概念虽然在面试题里不常被追问，但理解了这一层，你的认知深度就和只背答案的人拉开了差距。

我自己在面试候选人的时候，如果对方能自己推导出双指针解法，我会觉得这个人的“算法直觉”是到位的。如果对方只能答出两次遍历，我会引导一下：“能不能只遍历一次？”很多人在提示之后能反应过来，也有一些人在提示之后也写不对——他们已经背会了答案，却没理解答案背后的距离差逻辑。所以，这一题表面上是在考代码，实际上在考你是不是真懂。

4.4 来个递归视角的补充

还有第三类解法：递归。递归的思路是先递到链表末尾，然后在回溯过程中计数：

int kthToLastHelper(struct ListNode* head, int k, int* count) { if (head == NULL) { return -1; } int val = kthToLastHelper(head->next, k, count); (*count)++; if (*count == k) { return head->val; } return val; } int kthToLast(struct ListNode* head, int k) { int count = 0; return kthToLastHelper(head, k, &count); }

这个方案写起来很有趣，但有几个致命问题：一是递归深度等于链表长度，链表很长时会爆栈；二是它依赖回溯计数，逻辑上不如双指针直观。所以在面试里，递归可以作为“另一个思路”提一嘴，但我不建议把它作为主答案。除非面试官明确问“有没有不用循环的写法”，否则答递归反而会暴露你对空间复杂度的敏感性不够——递归的空间复杂度是 O(n)，而循环解法是 O(1)。

5. 边界条件与测试用例设计

5.1 必测的六个边界场景

写代码只是第一步，真正区分水平的是能不能面面俱到地把测试用例列出来。我一般会在面试前默写一套标准测试场景，这套场景在这道题里就是下面六个：

其中最容易翻车的是 k=1 和 k=链表长度这两个场景。k=1 时，如果某个解法里把 fast 先走的步数写成 k-1，那么得到的结果是倒数第 2 个节点，第一个用例就会挂。k=链表长度时，如果 fast 先走 k 步之后直接返回 slow->next，也会出错。关键时刻，这两条用例能把错误直接揪出来。

5.2 测试代码长什么样

以 C 语言为例，简单写一个测例：

#include <stdio.h> #include <stdlib.h> struct ListNode { int val; struct ListNode* next; }; struct ListNode* createNode(int val) { struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode)); node->val = val; node->next = NULL; return node; } void freeList(struct ListNode* head) { while (head != NULL) { struct ListNode* tmp = head; head = head->next; free(tmp); } } int main() { // 构造 1->2->3->4->5 struct ListNode* head = createNode(1); struct ListNode* p = head; for (int i = 2; i <= 5; i++) { p->next = createNode(i); p = p->next; } printf("k=2 -> %d (期望 4)\n", kthToLast(head, 2)); printf("k=5 -> %d (期望 1)\n", kthToLast(head, 5)); printf("k=1 -> %d (期望 5)\n", kthToLast(head, 1)); freeList(head); return 0; }

跑一遍，三个输出应该分别是 4、1、5。这一步过了，基本的正确性就有保障了。

5.3 空链表和 k 非法的返回约定

这里我想强调一个工程化的细节：面试题里“返回 -1 表示非法”是一种偷懒的约定，因为题目往往没规定 val 的取值范围。但在实际系统中，链表的 val 可能是任意 int 值，-1 完全有可能是合法数据。那么你要么使用一个独立的错误标志，要么改用返回结构体的方式：

struct Result { int val; int valid; // 1 表示有效，0 表示非法 };

面试时和面试官确认清楚这个约定，本身就是加分项——它展示了你对“函数接口健壮性”的思考。我见过不少候选人，代码完全正确，但只因在“返回什么表示非法”这件事上和面试官各说各话，浪费了不少时间。提前对齐，大家都舒服。

6. 面试现场：怎么把这题答出亮点

6.1 先说思路再动手

我见过太多面试者拿到题目就开始敲键盘，沉默了十分钟之后提交一段自己都觉得不太对的代码。正确做法是先把思路讲清楚：

• “我的第一反应是先遍历链表拿到长度，然后走 n-k 步就直接能取到目标节点。这样做时间复杂度 O(n)，空间 O(1)，但需要遍历两遍。”
• “为了让代码更优雅，我可以再用双指针优化：一个指针先走 k 步，然后两个指针同步走，快的到尾了，慢的就是答案。这样只用遍历一次。”

在你把“两次遍历”和“双指针”都写在纸面上之后，面试官会看到你有完整的思维链，而不是只会背一种解法。这个过程的收获比单纯写对代码要大得多。

6.2 主动给出测试用例

写完代码之后，不要傻坐着等面试官开口。你直接说：“我理了几个边界场景，k=1 要能取到最后一个节点，k=链表长度要能取到头节点，空链表和 k 越界要能返回错误。我先用这三个用例自查一下。”

这一句话一说出来，你的印象分就上去了。因为大部分面试者写完之后只会说“我觉得没问题”，只有少数人会主动验证。我不是说形式主义很重要，而是“主动验证”本身就是一种工程好习惯——写完代码不是终点，跑通用例才是。

6.3 如果面试官追问“链表长度未知怎么办”

双指针解法并不依赖链表长度，所以在“链表长度未知”这个前提条件下依然是正确答案。追问到这里，你正好可以进一步解释：“这种解法适合流式场景，因为不管链表多长，我只需要维护两个指针，在 fast 走到头时 slow 就定位到了目标节点。整个过程没有额外的存储开销。”

如果面试官继续追问“如果链表特别长，比如上亿个节点，有没有更快的办法”，你可以坦诚地分析：在单链表上找倒数第 k 个节点，任何算法都必须遍历一次才能知道链表的尾在哪里，所以时间下界就是 O(n)。不存在 O(log n) 的解法——因为链表缺少随机访问能力，你不可能跳过中间节点。这种“知道自己为什么做不到更好”的回答，比强答一个错的“优化方案”更显专业。

6.4 变体一刷：删除倒数第 k 个节点

这题在原题基础上多了一个“删除”动作，往往还要求只能遍历一次。思路和双指针一脉相承，唯一差别是：为了让 slow 停在“倒数第 k 个节点的前一个节点”，fast 需要先走 k+1 步。这样当 fast 走到 null 时，slow->next 正是要删的节点：

struct ListNode* removeNthFromEnd(struct ListNode* head, int k) { struct ListNode dummy; dummy.val = 0; dummy.next = head; struct ListNode* fast = &dummy; struct ListNode* slow = &dummy; for (int i = 0; i < k + 1; i++) { if (fast == NULL) { // k 非法 return head; } fast = fast->next; } while (fast != NULL) { slow = slow->next; fast = fast->next; } struct ListNode* toDelete = slow->next; slow->next = toDelete->next; free(toDelete); return dummy.next; }

这里用了一个虚拟头节点 dummy，目的是避免删除头节点时的特殊处理。这是链表面试题里一个非常常用的技巧——它把“头节点也可能被删”的边界情况统一处理了。你如果能主动写出 dummy 节点版本，面试官会意识到你处理链表时不是只会背模板。

6.5 变体二刷：求链表中点

求单链表的中点，也可以用双指针，只是这次两个指针的步长不同：slow 每次走一步，fast 每次走两步。当 fast 到尾时，slow 就是中点。这个思想跟“倒数第 k 个节点”一脉相承——都是利用两个指针之间的距离差来定位。

struct ListNode* middleNode(struct ListNode* head) { struct ListNode* slow = head; struct ListNode* fast = head; while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; } return slow; }

这个代码和“倒数第 k 个”相比，唯一差别在于 fast 的步长从“先走 k 步”变成了“每次走两步”。背后的本质仍然是距离差。你如果在面试里能把这两题关联起来讲，面试官对你的评价会从“会写题”上升到“理解模式”。

6.6 变体三刷：判断链表是否有环

判断链表是否有环，用的是同一个双指针框架：slow 每次走一步，fast 每次走两步。如果链表有环，fast 和 slow 终会相遇；如果无环，fast 会先走到 NULL。

int hasCycle(struct ListNode* head) { struct ListNode* slow = head; struct ListNode* fast = head; while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; if (slow == fast) { return 1; } } return 0; }

这道题在“倒数第 k 个”的基础上，又多了一层“为什么快慢指针一定会相遇”的数学论证。但它用的还是那个核心框架：两个指针，一段距离差，一个明确的终止条件。一法通，万法通，就是这个意思。

7. 高频踩坑点与经验总结

7.1 读题不清：k 的计数起始值搞错

这是最最常见的翻车点。题目里如果写的是“倒数第 k 个”，k 通常从 1 开始；但有些练习题或变体里写的是“倒数第 k 个节点，k 从 0 开始”。两者代码差距只有一步，却会导致结果完全不同。我的建议是：不管你刷过多少遍这题，每次拿到题目都先确认一下“k 的语义”再动手。

注意：如果题目说“返回倒数第 k 个节点”，且没有特别说明 k 的起始值，默认从 1 开始。面试时口头和面试官确认一次，不吃亏。

7.2 空指针解引用

在双指针版本里，fast = fast->next这一步如果 fast 已经为 NULL 就会崩溃。所以在 fast 先走 k 步的循环里，每一步都要检查fast == NULL。很多同学在“While fast != NULL”的主循环里记得判断，偏偏在“先走 k 步”的阶段不判断，一旦 k 大于链表长度，当场崩溃。这个细节虽然简单，但代码写快了很容易忽略。

7.3 面试不要只给一个解法

就算你只会双指针，也最好提一嘴“还有一种朴素做法是两次遍历”。因为你展示的不是“我知道最优解”，而是“我理解这个问题域”——哪一种解法在什么场景下适用，各有什么取舍。这种思维在系统设计面试里会更吃香，但在算法题里同样能体现功底。

7.4 刷题建议：画图

链表题的抽象性很强，尤其是双指针这种“看代码觉得挺对，但说不清为什么”的题目，我强烈建议你在草稿纸上画图。画出链表节点、画出 slow 和 fast 每一步的位置，跑五到六个节点的小例子，你就能直观感受到那个“距离差窗口”是怎么滑到倒数第 k 个位置的。这个习惯帮我解决过很多链表题，比盲目刷十道题都管用。

7.5 从面试题到工程思维

说句掏心窝的话：现实中几乎没有人会真的让你写一个“返回链表倒数第 k 个节点”的函数。但这个题背后的能力模型，在真实系统里每天都在被调用。比如消息队列的批量消费、日志文件的尾部追踪、缓存淘汰策略里某些场景的指针维护，本质上都是这种“在单向流式数据里定位某个位置”的问题。

我后来带新人时，总喜欢拿这道题当开场白——不是因为它是所谓的高频题，而是因为它能把“数据结构的理解”“边界条件的敏感度”“算法优化的直觉”“代码实现的稳健性”一次性全测出来。一个候选人如果在这道题上表现得既快又稳，那他在后续更复杂的算法题上通常也不会差。

最后分享一个我自己刷题的仪式感：每做完一道链表题，我都会自己写出三个“变态用例”再跑一遍——空链表、超长链表、k 恰好是链表长度。这不只是在验证代码，更是在培养一种肌肉记忆：算法不是只跑通 happy path 就结束的，真正的稳定恰恰来自那些没人注意的角落。希望读完这篇文章的你，也能养成这个习惯。