Appearance
2009·42 倒数第 k 个结点：从两遍扫描到双指针
本文属于「从暴力解到最优解」专题。这是全专题里暴力解和最优解离得最近的一道题：暴力解已经是
时间、 空间，最优性档卡的只剩「扫两遍还是扫一遍」。也正因为差距小，这次升级几乎是白捡的——而它练出来的双指针，是后面一串链表题的地基。
题目
已知一个带有表头结点的单链表，结点结构为：
┌──────┬──────┐
│ data │ link │
└──────┴──────┘假设该链表只给出了头指针 list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第 k 个位置上的结点（k 为正整数）。若查找成功，算法输出该结点的 data 域的值，并返回 1；否则，只返回 0。要求：
(1) 描述算法的基本设计思想。 (2) 描述算法的详细实现步骤。 (3) 根据设计思想和实现步骤，采用程序设计语言描述算法（使用 C、C++ 或 Java 语言实现），关键之处请给出简要注释。
总分 15 分。题面写了「尽可能高效」——按总纲的分类，最优性分存在；同时注意另一个硬约束：不改变链表，任何版本都只能读、不能写。
第一步：把暴力解写对
「倒数第 k 个」换算成正数很简单：链长为 n 时，倒数第 k 个就是正数第 n − k + 1 个。麻烦在于单链表不自带长度——那就先扫一遍数出来：
- 第一遍：从首结点走到尾，数出长度 n；
- 判断：若 k > n，链不够长，返回 0；
- 第二遍：从首结点再出发，走 n − k 步，落点就是倒数第 k 个。
c
typedef struct LNode {
int data;
struct LNode *link;
} LNode, *LinkList;
int findKthFromTail(LinkList list, int k) {
// ① 第一遍：数出链表长度 n（从 list->link 起，不含头结点）
int n = 0;
for (LNode *p = list->link; p != NULL; p = p->link) n++;
if (k > n) return 0; // 链长不足，查找失败
// ② 第二遍：从首结点走 n - k 步，到达正数第 n-k+1 个
LNode *p = list->link;
for (int i = 0; i < n - k; i++) p = p->link;
printf("%d", p->data); // 输出倒数第 k 个结点的 data
return 1;
}拿链 1 → 2 → 3 → 4 → 5 → 6、k = 2 走一遍：第一遍数出 n = 6；6 ≥ 2 不越界；第二遍走 4 步落在值为 5 的结点上，输出 5 返回 1 ✓。k = 7 时 n = 6 < 7，直接返回 0 ✓。k = n = 6 时走 0 步，落在首结点 ✓。
复杂度：两遍各走一次链，时间
它值多少分
按正确性/最优性两个维度（详见总纲）：
- 正确性：这份解能正确定位倒数第 k 个结点、k 越界时返回 0、成功时输出 data 返回 1、不改动链表——正确性维度的主体分都拿得到。题库解析里也明说了：先求长度再走 n − k 步的两遍扫描「也对」。
- 最优性：题面「尽可能高效」在这道题上的判据是扫描遍数——双指针一遍扫描是标答，两遍扫描在最优性上按「扫一遍 vs 扫两遍」丢一小档。
这是全专题里暴力解最保值的一道：渐进复杂度已经和最优解持平，丢的只是最优性里很小的一档。复杂度那问照实写「两遍扫描、时间
暴力解的浪费在哪
用总纲的「找浪费三问」审一遍：
有没有重复扫描？——有。整条链被走了两遍，而第一遍走完只带走一个数字 n，沿途看到的所有结点位置信息全部扔掉了，第二遍只能从头再来。
有没有放着性质不用？——有，而且就是解题钥匙。「倒数第 k 个」的本质是「距离链尾恰好 k 个结点」。要判断这件事，其实不需要知道总长 n——只要有另一个游标在前面 k 步替你探路：探路的到了链尾，你就正好在倒数第 k 个。「先数 n 再算 n − k」是绕了远路，把一个相对位置问题做成了绝对位置问题。
对策就是总纲的第一类手段——一遍扫描时多记一点：多带一个指针，把「距离」直接编码在两个指针的间隔里。
智慧化改造：双指针一遍扫描
让 fast、slow 都从首结点出发：fast 先走 k 步，然后两人同步前进、始终保持 k 个结点的间距。当 fast 越过链尾（NULL）时，slow 距链尾正好还差 k——它就是倒数第 k 个。若 fast 在先走的 k 步里就撞上 NULL，说明链长 < k，返回 0。
数学上验证一下：链长 n，fast 先走 k 步后，两人再同步走 n − k 步 fast 到达 NULL，此时 slow 从首结点走了 n − k 步，指向正数第 n − k + 1 个，正是倒数第 k 个。
c
typedef struct LNode {
int data;
struct LNode *link;
} LNode, *LinkList;
int findKthFromTail(LinkList list, int k) {
LNode *fast = list->link; // 跳过头结点，从首结点开始
LNode *slow = list->link;
int i = 0;
// ① fast 先走 k 步；若途中遇 NULL，说明链表长度 < k
while (fast != NULL && i < k) {
fast = fast->link;
i++;
}
if (i < k) return 0; // 长度不足，查找失败
// ② 两指针同步前进，fast 到 NULL 时 slow 即倒数第 k 个
while (fast != NULL) {
fast = fast->link;
slow = slow->link;
}
printf("%d", slow->data); // 输出倒数第 k 个结点的 data
return 1;
}复杂度：fast 总共走完整条链一次（前 k 步 + 后 n − k 步 = n 步），时间
从两遍扫描升级过来，四个细节决定这 15 分能拿多满：
- fast 先走 k 步，不是 k − 1 步。间距必须恰好是 k：fast 到 NULL 那一刻 slow 才落在倒数第 k 个上。先走 k − 1 步会让 slow 停在倒数第 k + 1 个，差一个结点。
- 越界判定藏在先走的循环里。循环条件写
fast != NULL && i < k，走完检查i < k就返回 0。漏掉这个判定，链长不足时会带着错误状态进入同步循环，逻辑全乱——这是本题最常见的丢分点。 - 从
list->link起步，不是list。题面是带头结点的链表，头结点不存数据；从 list 起算会整体错位一个结点。 - 只读不写。「不改变链表」是题面硬约束，fast、slow 只是游标，不能改 link 域、不能 malloc/free。两遍扫描版天然满足，双指针版也一样——升级不引入任何写操作。
两版对照跑一遍
同一条链 1 → 2 → 3 → 4 → 5 → 6，k = 2，答案是值为 5 的结点。先看两遍扫描版——注意链被完整走了两轮：
再看双指针版——fast 先拉开 k 的间距，然后两个指针齐步走，一遍到位：
演示为不带头结点的 JavaScript 等价版本，成功时直接返回查到的 data 值；考卷上请按题面用带头结点写法（上文 C 代码），输出 data 并返回 1/0。
等价方法与升级空间
- 栈法：把所有结点依次压栈，再弹 k 次，弹出的就是倒数第 k 个。定位正确，拿正确性分；但辅助栈占
空间，按算法欠最优在最优性上丢分——它比两遍扫描丢得更多，因为两遍扫描至少空间是 的。 - 双指针的一套家族：本题的「fast 提前 k 步」和「fast 走 2 步 slow 走 1 步找中点」「快慢指针判环」是同一个技巧的三个变体。找中点那个变体正是 2019·41 链表重排三步原地解的第一步——这道 2009 年的题，练的是后面十几年反复出现的基本功。
下一步
- 在 OJ 上把两版代码都提交跑一遍：ds-2009-42 倒数第 k 个结点
- 回到题库看这道题的完整解析与错因：真题库 · 数据结构