题目

已知一个带有表头结点的单链表，结点结构为：

┌──────┬──────┐
│ data │ link │
└──────┴──────┘

假设该链表只给出了头指针 list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第 k 个位置上的结点（k 为正整数）。若查找成功，算法输出该结点的 data 域的值，并返回 1；否则，只返回 0。要求：

(1) 描述算法的基本设计思想；

(2) 描述算法的详细实现步骤；

(3) 根据设计思想和实现步骤，采用程序设计语言描述算法（使用 C、C++ 或 Java 语言实现），关键之处请给出简要注释。

解析

(1) 设计思想

答案：双指针法——用 fast、slow 两个指针都从首结点出发；fast 先走 k 步，然后 fast 和 slow 同步前进；当 fast 走到 NULL（链尾后）时，slow 恰好指向倒数第 k 个结点。

为什么这样能定位倒数第 k 个？

让 fast 比 slow 提前 k 步出发——两指针之间始终保持 k 个结点的距离。当 fast 走到 NULL（即超出最后一个结点）时，slow 距离链尾还有 k 个结点的距离，正好是倒数第 k 个。

数学上：设链表长度 n（不含头结点）。倒数第 k 个 = 正数第 n − k + 1 个。让 fast 先走 k 步后两人同步前进：当 fast 走完 n − k 步到达 NULL 时，slow 走了 n − k 步，从首结点开始数就是第 n − k + 1 个结点，正好。

异常情况——k 大于链表长度：fast 在前 k 步预先走时就遇到 NULL（链不够长），此时直接返回 0 表示查找失败。

(2) 详细实现步骤

1. 设 fast = list->next（首结点），slow = list->next，计数器 i = 0；
2. 让 fast 先走 k 步——循环 while (fast != NULL && i < k)：fast = fast->next，i++；
3. 走完上述循环后判断：若 i < k，说明链表长度 < k，返回 0；
4. 否则，fast 和 slow 同步前进——while (fast != NULL)：fast = fast->next，slow = slow->next；
5. 循环结束，fast 已到 NULL，slow 指向倒数第 k 个结点，输出 slow->data 并返回 1。

(3) 代码实现

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;
}

关键点说明：

• 不能修改链表：题面要求"不改变链表"——本算法只读不写，slow 和 fast 只是普通游标。
• 跳过头结点：题面是"带表头结点"的单链表，遍历从 list->link 开始（list 是 dummy 头）。
• 为什么 fast 先走 k 步而不是 k-1 步？ 让两指针保持 k 距离：fast 在 slow 前面 k 个结点。fast 越界（NULL）那一刻，slow 离链尾还差 k − 1 步，正好是"倒数第 k 个"。如果让 fast 先走 k-1 步，slow 会指向倒数第 k+1 个，差一个。
• 复杂度：时间 O(n)（fast 总共走完整个链一次，每个结点被访问 O(1) 次）；空间 O(1)（只有 fast、slow、i 三个标量）。
• 替代方法——两遍扫描：先扫一遍数出长度 n，再走 n − k 步。也对，但是要扫两遍；双指针只扫一遍，更优。

编者注（生僻术语）：「双指针 / 快慢指针」是单链表场景的万能技巧——找中点（fast 走 2 步、slow 走 1 步）、找环（slow 与 fast 重合则有环）、找倒数第 k 个（fast 提前 k 步），三个都是它的变体。考研、面试都常考，记牢一套基本公式可以一并解决。