链表中倒数第k个结点：双指针解法与边界条件详解

刷题的人应该都见过这道题链表中倒数最后k个结点。牛客上标的是简单档位剑指Offer里也有它但我在面试中实际问下来能把这道题讲清楚、写对的人十个里大概两三个。多数情况是背出了双指针的代码问一句“为什么快指针先走k-1步”对方就卡住了——这说明他只是记住了步骤没有真正理解指针移动的规律。这篇内容主要写给三类人准备笔试面试、正在刷链表题的同学学数据结构时想搞懂单链表指针操作的人以及想通过一道题把“快慢指针”这类算法思想彻底吃透的开发者。我会先把这个题的定义陷阱说清楚再推演两次遍历和双指针两种解法接着把边界条件一个个列出来最后聊聊快慢指针在判环、找中点、删除结点等场景里的延伸应用以及我自己提交过程中踩过的坑。保证看完之后你不仅能AC这道题还能把同一个思路迁移到其他链表问题上。1. 这道“简单题”到底在考什么先看清倒数第k个的定义陷阱1.1 题目描述与两种常见版本先看标准描述输入一个链表输出该链表中倒数第k个结点。例如链表是1-2-3-4-5倒数第3个结点是值为3的结点。注意这里的关键约定计数从1开始倒数第1个是最后一个结点也就是值为5的那个。这是整道题的地基后边的代码全都建立在这个定义之上。很多人在这个地方栽跟头不是不会写指针而是没搞明白“倒数第k个”到底是从哪里开始数的。还有个容易忽略的点不同平台对这个题目的描述可能有细微差别。牛客网原题会明确说“如果k小于0或k大于链表长度返回NULL”力扣上更常见的是一道变形题“删除链表的倒数第N个结点”它保证了N一定合法个别教材甚至会把“尾结点”定义为倒数第0个。这些差异会导致代码里的偏移量相差1。我的习惯是动手前先确认计数规则并在函数注释里写清楚“倒数第1个是尾结点”防止写到一半自己迷糊。1.2 为什么这道题值得单独写一篇从数据结构课程角度看它考察的是单链表只能单向遍历、没有随机访问这个基本特性。数组里要取倒数第k个直接算下标len-k就能拿到链表没有下标只能通过指针移动来找。这是链表和数组最本质的区别之一也是很多初学者从数组思维转向链表思维时遇到的第一道坎。从面试角度看这道题的价值在于它自然引出了双指针思想。链表类问题里有大批题目都建立在双指针之上判断链表是否有环、寻找链表中点、寻找两个链表交点、删除倒数第N个结点。可以这么理解这道题是“钥匙题”把它的指针移动规律吃透了后面那些题目的学习成本会低很多。我见过不少候选人链表基础题都靠背到了判环、找交点这种稍微变形的问题就完全没思路本质上是没弄明白双指针为什么能工作。1.3 最直觉的暴力思路两次遍历拿到这道题大多数人第一反应是先遍历一遍链表数出一共有多少个结点拿到长度len然后判断k是否合法最后从头结点再走len-k步就是倒数第k个。这个思路没有任何问题代码也不容易出错。但它有一个隐含前提链表长度必须预先知道而且两次遍历之间链表结构不能发生变化。如果链表很长比如几十万甚至上百万个结点两次遍历的成本就不能忽略。如果链表头指针会被其他线程修改两次遍历之间数据可能已经变了拿到的结果自然不准确。面试官看到两次遍历通常不会说错但大概率会追问一句“能不能只遍历一次就把结果找出来”。这时候就需要双指针登场了。2. 从两次遍历到双指针一步步把复杂度降下来2.1 两次遍历法先求长度再定位先给出两次遍历的C语言实现这是最容易被理解、也最适合作为正确性基准的版本struct ListNode { int val; struct ListNode *next; }; struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) { if (pListHead NULL || k 0) { return NULL; } int len 0; struct ListNode* p pListHead; while (p ! NULL) { len; p p-next; } if (k len) { return NULL; } int steps len - k; p pListHead; while (steps 0) { p p-next; steps--; } return p; }这里需要解释一个很容易搞混的点为什么从头结点走len-k步就能到达倒数第k个结点假设链表有len个结点采用从1开始计数的规则。头结点是正数第1个倒数第k个结点就是正数第len-k1个。从头结点到正数第len-k1个结点需要走len-k步。以1-2-3-4-5为例len5k2时len-k3从头结点走3步到达结点4而结点4正是倒数第2个。这个推演建议在纸上画一遍比死记公式有用得多。复杂度方面时间O(n)空间O(1)。有读者可能会问双指针不也是O(n)吗两个解法有什么区别区别在于“遍历次数”。渐进复杂度相同但双指针只需要一次遍历而且它为后续的删除倒数第N个结点、判环等变形题提供了统一的思维框架。2.2 双指针法为什么快指针先走k-1步双指针的核心思想用一句话概括就是维持两个指针在链表上的距离为k-1。具体步骤分三步快指针先从头结点出发走k-1步到达正数第k个结点。此时快慢指针之间相距k-1个结点。如果途中遇到NULL说明k大于链表长度直接返回NULL。然后快慢指针同步前进每次都走一步保持距离k-1。当快指针到达尾结点fast-next NULL时慢指针自然就落在倒数第k个结点上。为什么是k-1而不是k关键在于两个指针的初始距离是0。如果快指针先走k-1步两个指针的距离是k-1如果先走k步距离就是k。当快指针到达尾结点时慢指针与快指针相距k-1那么慢指针距离尾结点就是k-1换句话说慢指针是倒数第k个。如果快指针先走k步同步走完时慢指针距离尾结点是k那它就是倒数第k1个——这就多走了一位。2.3 双指针法的C语言实现给出我推荐的标准写法struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) { if (pListHead NULL || k 0) { return NULL; } struct ListNode* fast pListHead; struct ListNode* slow pListHead; // 快指针先走k-1步 for (int i 0; i k - 1; i) { if (fast-next ! NULL) { fast fast-next; } else { // 还没走完k-1步就遇到链表尾部说明k大于链表长度 return NULL; } } // 快慢指针同步走快指针到达尾结点时慢指针正好是倒数第k个 while (fast-next ! NULL) { fast fast-next; slow slow-next; } return slow; }这个版本我建议直接背下来。它的好处是逻辑清晰for循环负责让快指针先走边走边检查是否越界while循环负责同步前进。两个循环的职责分明不容易出错。2.4 另一种等价的k步写法网上还能看到另一种写法快指针先走k步struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) { if (pListHead NULL || k 0) { return NULL; } struct ListNode* fast pListHead; struct ListNode* slow pListHead; // 快指针先走k步 for (int i 0; i k; i) { if (fast ! NULL) { fast fast-next; } else { return NULL; } } // 如果fast已经为NULL说明k等于链表长度倒数第k个就是头结点 if (fast NULL) { return pListHead; } // 同步走fast走到NULL时slow正好是倒数第k个 while (fast ! NULL) { fast fast-next; slow slow-next; } return slow; }这个版本也是对的但有两个地方需要特别注意。第一它里面的循环条件和前一个版本不一样。前一个版本用fast-next NULL作为终止条件这个版本用fast NULL作为终止条件。原因是快指针先走的步数不同导致最终判断位置不同。第二如果快指针走完k步后fast恰好是NULL说明k等于链表长度倒数第k个就是头结点。这个if (fast NULL) return pListHead;特判千万不能漏。一旦漏掉后面的while循环根本不会执行函数会错误地返回NULL。这两种写法结果一致但我个人更推荐前一版先走k-1步因为它的逻辑更直观可以少处理一个特殊情况。如果你想在面试中展示自己对指针关系的理解建议把前一版讲透。3. 边界条件是真正的考点五个用例一次性想清楚3.1 五个边界用例逐一看很多人代码写对了却在边界用例上翻车。我把这道题需要覆盖的边界条件整理成一张表每个用例都对应代码里的一个分支用例输入期望结果容易犯的错误空链表pListHead NULLk 任意值NULL直接解引用pListHead-next程序崩溃k 0k 0 或 k -1NULL把k0当k1处理返回尾结点k 1链表非空尾结点快指针先走k-1步走0步正确返回尾结点k 链表长度链表为1-2-3k3头结点快指针走2步到尾部while不执行slowhead正确处理k 链表长度链表为1-2-3k5NULL快指针在for循环中遇到NULL返回NULL表格看下来好像很简单但实际的坑在于很多人只在OJ上跑了一个正常用例就提交了结果k0的时候直接取到尾结点k大于链表长度的时候程序崩溃。尤其是“k大于链表长度”这个用例是双指针实现里最容易被忽视的。3.2 为什么越界判断必须在指针移动过程中做对于双指针法k大于链表长度的情况只能在移动过程中发现。快指针从头部开始目标是走k-1步但链表长度不够走到某个位置时fast-next已经是NULL了。这时候必须立刻返回NULL而不是继续尝试移动。这个判断必须写在for循环内部而且是每次移动前先检查。有些初学者会在for循环结束后才想起来判断fast是否为空但那时候可能已经对空指针做了fast-next解引用——整个程序已经崩溃了。对比两次遍历法它的越界判断是在第一次完整遍历结束后做的根据len和k的大小关系判断。这两种做法都没错但面试时如果你能把双指针版本里的越界处理讲清楚会是一个加分项。3.3 实际OJ平台上的细节差异不同平台对非法输入的处理要求不完全一样。牛客的题目会明确说k小于0或k大于链表长度时返回NULL力扣的删除倒数第N个结点题则保证N是合法的不需要考虑越界还有些平台允许多次调用同一个函数但对时间有要求两次遍历可能会超时。我的建议是读题阶段先弄清楚两件事——k的取值范围是否合法以及函数在非法输入下应该返回什么。不要想当然地用一套代码通吃所有平台。另外如果题目要求你在O(n)时间和O(1)空间内完成两次遍历其实也满足但如果面试官追问“能否只遍历一次”你就需要给出双指针解法。4. 快慢指针不是一道题的答案是一类题的钥匙判环、中点、删除结点理解了倒数第k个之后你会发现快慢指针这个思想在链表题里无处不在。这里我挑三个最典型的应用展开每一个都能在倒数第k个的基础上找到对应关系。4.1 寻找链表的中点需求找出链表的中点结点。思路快指针每次走两步慢指针每次走一步。当快指针到达链表尾部时慢指针正好在中点附近。具体来说如果链表长度为奇数比如1-2-3-4-5快指针到尾部时慢指针在结点3正好是中点。如果链表长度为偶数比如1-2-3-4慢指针会落在结点3也就是中间两个结点里的后一个。如果想取前一个调整循环条件即可。这个技巧在“将链表对半拆分”“归并排序找分割点”等场景里很常用。它和倒数第k个的联系在于快慢指针的步速比不同最终慢指针的位置也不同。倒数第k个是快指针先走k-1步然后同步走找中点是快指针始终走两步慢指针走一步。核心都是“利用速度差控制两个指针的相对位置”。4.2 判断链表是否有环判断一个链表里是否存在环经典解法也是快慢指针。快指针每次走两步慢指针每次走一步。如果链表中存在环快慢指针最终会在环内相遇如果快指针先到达NULL说明链表没有环。为什么这个方案可行关键在相对速度。进入环之后快指针相对于慢指针的速度是每步1个结点也就是说每走一步两者之间的距离就缩短1不可能跳过去最终一定会追上。这跟倒数第k个里的“同步走、保持距离”形成了很好的对比一个是保持距离一个是缩小距离。需要说明的是快指针走两步、慢指针走一步是最常用的搭配。如果快指针走三步追上慢指针的概率依然存在但可能有跳过的情况代码复杂度也会上升。所以面试时不要为了炫技去改倍数老老实实用1和2。4.3 删除倒数第N个结点从查找变成删除力扣第19题“删除链表的倒数第N个结点”是这道题最常见的变形。思路仍然是双指针但要注意一个区别删除一个结点光找到它还不够必须找到它的前驱。倒数第N个结点的前驱是倒数第N1个结点。所以操作顺序调整为快指针先走N1步然后快慢指针同步走当快指针到达NULL时慢指针正好是倒数第N1个结点。此时执行slow-next slow-next-next即可完成删除。这里有个经典的坑如果要删除的是头结点它没有前驱。解决方案是引入一个dummy结点指向头结点从dummy出发走N1步最终dummy-next指向的就是被删除的倒数第N个结点。这种“虚拟头结点”的技巧在处理链表头结点的增删操作时非常通用建议熟练掌握。4.4 从链表走到数组滑动窗口的双指针思想快慢指针并不只在链表里出现。数组里常见的滑动窗口本质上也依赖两个指针的配合一个右指针负责扩展窗口一个左指针负责收缩窗口两者共同维护一个满足条件的区间。举一个最简单的例子求数组中不超过某个长度的最长连续子数组。暴力做法是枚举所有起点和终点O(n^2)复杂度滑动窗口做法是右指针往前扩展一旦窗口不合法就移动左指针收缩每个元素最多进窗口一次、出窗口一次总复杂度降为O(n)。这和链表里的快慢指针有异曲同工之处都是通过两个指针的配合避免重复遍历已经处理过的区域。在面试中如果你能在讲完倒数第k个之后举出滑动窗口的例子面试官通常会觉得你对双指针思想的理解是成体系的而不是孤立地背题。5. 提交记录里的真实经验三个典型错误和一套验证方法5.1 典型错误一倒数第k个写成了倒数第k1个这个错误在OJ上表现得很隐蔽。链表1-2-3-4-5k2正确输出应该是结点4。如果你写的版本是“快指针先走k步然后同步走到fastNULL最后返回slow”结果返回的是结点5。原因在前文已经分析过快指针先走k步两个指针之间的距离就是k。同步走到终点时慢指针距离尾结点还有k个位置那它自然就是倒数第k1个。修正方法有两种把先走的步数改为k-1或者走k步后特判fast为NULL时返回头结点。我推荐第一种少一个特判分支。5.2 典型错误二没有处理k大于链表长度的情况这个错误会直接导致程序崩溃。假设链表只有3个结点k5。快指针目标是走4步但走到第3步时fast-next已经是NULL如果再执行fast fast-next解引用空指针程序当场崩溃。正确的做法是在for循环内部每次移动前检查fast-next是否为空。如果为空就直接返回NULL不要继续走。这个分支看似简单但在紧张状态下特别容易漏写。我自己早期刷题时就因为漏了这个判断在本地编译器上跑通了放到OJ上就崩。5.3 典型错误三指针变量命名混乱导致逻辑分叉有同学写链表操作时习惯用p、q、r这种单字母命名写短链表还好写复杂逻辑时自己都分不清哪个是快指针、哪个是慢指针。我见过最离谱的版本是用p和q命名结果在while循环里把p和q都更新了一遍最后返回了一个完全无关的结点。我自己的习惯是只要涉及两个指针一律命名为fast和slow如果涉及三个以上指针用prev、cur、next这种带语义的命名。代码可读性提升之后调试成本会下降很多。这个习惯在笔试手写代码时尤其重要——面试官看的就是你组织的代码是否清晰可维护。5.4 一套快速验证用例分享一套我常用的本地验证方法。写一个main函数手动构造链表1-2-3-4-5然后依次调用k0、k1、k3、k5、k6五个用例再构造一个空链表调用k1。#include stdio.h #include stdlib.h struct ListNode { int val; struct ListNode *next; }; struct ListNode* createList(int arr[], int n) { struct ListNode dummy; struct ListNode* tail dummy; for (int i 0; i n; i) { struct ListNode* node (struct ListNode*)malloc(sizeof(struct ListNode)); node-val arr[i]; node-next NULL; tail-next node; tail node; } return dummy.next; } int main() { int arr[] {1, 2, 3, 4, 5}; struct ListNode* head createList(arr, 5); struct ListNode* result FindKthToTail(head, 3); if (result ! NULL) { printf(k3, expected 3, got %d\n, result-val); } else { printf(k3, expected 3, got NULL\n); } result FindKthToTail(head, 1); if (result ! NULL) { printf(k1, expected 5, got %d\n, result-val); } else { printf(k1, expected 5, got NULL\n); } result FindKthToTail(head, 5); if (result ! NULL) { printf(k5, expected 1, got %d\n, result-val); } else { printf(k5, expected 1, got NULL\n); } result FindKthToTail(head, 0); printf(k0, expected NULL, got %s\n, result NULL ? NULL : not NULL); result FindKthToTail(NULL, 1); printf(empty list, expected NULL, got %s\n, result NULL ? NULL : not NULL); return 0; }这五个用例覆盖了正常位置、尾结点、头结点、非法k值、空链表五个关键场景。只要能全部通过代码上线OJ基本不会有问题。很多同学只测一个k2就觉得完事了这是最危险的习惯——边界用例远比正常用例更能反映代码质量。这道题虽然简单但它是理解链表双指针思想的一块敲门砖。把“为什么快指针先走k-1步”和“k大于链表长度怎么办”这两个问题想明白再去碰判环、找中点、删除倒数第N个结点你会发现它们背后其实是一个思路。