面试题22：链表中倒数第k个节点

从“倒数第1个是谁”开始

快慢指针是本题的核心：

先预测：链表 1→2→3→4→5 中，倒数第1个是5，倒数第2个是4，倒数第5个是1；倒数第0个没有意义。作者明确从1开始计数，这个决定了快指针应领先多少步。

若先遍历得到长度 n，目标正数位置是 n-k+1，再从头走一遍即可。但题目希望单遍扫描。单向链表不能从尾部向前走，所以需要在第一次经过节点时保留一个与尾部相对距离有关的位置。

让 ahead 与 behind 都从头开始，ahead 先走 k-1 条 next 边。之后两者同步前进；ahead 到达尾节点时，behind 就是链表中倒数第k个节点。两个速度相同但保持固定距离的位置称为固定间隔。

这里“快”不是每轮走两步，而是先启动 k-1 步；同步阶段两者速度相同。快慢只是相对起点不同。把它和判圈算法中一倍、两倍速度的快慢指针混为一谈，容易写错间隔。

为什么必须保持k-1条边

长度为 n 的链表中，倒数第k个节点是正数第 n-k+1 个。behind 从第1个节点走到这里需要 n-k 步。ahead 先到第k个节点，随后再走 n-k 步，恰好到第n个尾节点。

因此两个指针的是 k-1 条边，或等价地说两端之间覆盖 k 个节点。原书要点“保持k-1个节点间隔”在这里指两个位置相差k-1次next移动。k=1 时领先0条边，两指针重合并最终一起到尾；k=n 时 ahead 先行到尾，behind不再移动并返回头。

如果误让 ahead 只领先 k-2 条边，结果会比目标靠后一个节点；若领先 k 条边却仍以 ahead 停在尾为终点，结果会靠前一个节点。领先距离与终止条件必须配套。

作者版本：先行k-1步，停在尾节点

作者接收无符号 k，因此先检查 k==0。先行循环每次在访问 next 前确认仍有后继；若无法走满 k-1 步，说明链表不足k个节点，返回空。

struct ListNode {
    int value;
    ListNode* next = nullptr;
};
 
ListNode* findKthToTail(ListNode* head, unsigned int k) {
    if (head == nullptr || k == 0) return nullptr;
 
    ListNode* ahead = head;
    for (unsigned int i = 0; i < k - 1; ++i) {
        if (ahead->next == nullptr) {
            return nullptr;
        }
        ahead = ahead->next;
    }
 
    ListNode* behind = head;
    while (ahead->next != nullptr) {
        ahead = ahead->next;
        behind = behind->next;
    }
    return behind;
}

同步循环检查 ahead->next，所以结束时 ahead 仍指向尾节点而不是空。behind 与它相差 k-1 条边，于是返回目标。当前写法中 ahead 在入口非空，先行阶段也从不把它赋为空，因此循环解引用安全。

等价版本：先行k步，走到空指针

另一种常见写法让 ahead 先走 k 步。若途中为空但还没走完，长度不足；先行成功后 behind 从头开始，两者同步直到 ahead 为空。这时 ahead 比 behind 领先 k 条边，behind 正好位于倒数第k个。

#include <cstddef>
 
const ListNode* kthFromEnd(const ListNode* head, std::size_t k) {
    if (head == nullptr || k == 0) return nullptr;
 
    const ListNode* ahead = head;
    for (std::size_t step = 0; step < k; ++step) {
        if (ahead == nullptr) return nullptr;
        ahead = ahead->next;
    }
 
    const ListNode* behind = head;
    while (ahead != nullptr) {
        ahead = ahead->next;
        behind = behind->next;
    }
    return behind;
}

这两个版本都正确，但不能拿第一个版本的先行 k-1 步搭配第二个版本的走到空，或反过来。面试时先写清“间隔是几条边、终点是尾节点还是空”，再落循环条件，可以消除off-by-one。

返回 const ListNode* 能表达函数只观察链表，不修改节点。若调用者需要可变节点，可提供重载或返回 ListNode*；不应为了方便在只读接口中去掉 const。

三类防御检查对应三种失败

空链表没有任何节点，立即返回空；k=0违反从1开始的计数规则，立即返回空；k大于长度则在先行阶段发现后继不足。也就是说，“k非法与链表不足k个节点”是两种不同失败：前者在入口拒绝，后者在先行过程中识别。把这些入口和过程检查称为。

作者使用 unsigned int，函数内部不可能收到负数，但外部若把 -1 直接转换为无符号，会变成一个巨大值，先行循环可能遍历到尾后返回空，却掩盖参数错误。用户输入应先以有符号整数或文本解析，验证 k 大于0且不超过接口上限，再转换。

还要注意 k-1 的无符号下溢。作者先检查 k==0，再进入以 k-1 为上界的循环，所以安全。若把检查删掉，0-1 会变成无符号最大值，循环会尝试大量迭代并很快在指针上失败或崩溃。

单遍扫描的真实含义

算法中 ahead 与 behind 各自访问一部分链表，但没有先完整计数再重新从头扫描。每条 next 边被访问常数次，总工作量不超过约两倍长度，仍属于和 O(n) 时间。

辅助状态只有两个指针、循环计数和 k，额外空间 O(1)。链表不可随机访问，且目标依赖尾部位置；在不知道长度时，任何正确算法都必须观察到尾部，因此 O(n) 时间是必要的。

如果会对同一不变链表查询很多不同 k，可先把节点地址存入数组，预处理 O(n) 时间和 O(n) 空间，之后每次 O(1) 查询；或让容器维护长度，再按较小方向选择结构。单次查询时，额外索引通常得不偿失。

有环链表会破坏终止性

作者默认输入是无环单向链表。若存在环，ahead->next 永远不为空，同步循环不会结束；“倒数第k个”本身也因没有尾节点而无定义。接口必须由链表类型保证无环，或在不可信输入上先运行判圈。

先判圈再定位需要额外一次遍历，但这是不同契约的必要成本。不能把 Floyd 判圈指针与本题固定间隔指针混在一个循环里后仍声称简单正确；两个不变量不同，应分阶段完成。

并发线程若在扫描时删除节点，ahead 或 behind 可能悬空；若追加节点，尾部位置还会变化。裸链表版本要求遍历期间结构不变，并由调用方持有锁或独占所有权。原子 next 本身不能解决节点回收。

节点值与节点身份

函数应返回目标节点地址，而不只是值。链表可能含重复值，例如 1→4→4→5，倒数第3和倒数第2的值都为4，却是不同物理节点。测试只比较 value 可能无法发现返回了错误的重复节点。

因此测试夹具应保存每个构造节点的地址，并断言结果恰好等于期望地址。结果是借用指针，链表销毁后立即失效；函数不转移所有权，调用者不能单独 delete 返回节点。

若容器使用 unique_ptr 拥有 next，遍历可通过 get 取得只读观察指针；返回裸 const 指针仍是非拥有借用。需要跨容器变更长期保存结果时，应使用稳定句柄或共享所有权策略，而不是假设裸地址永久有效。

作者六组测试覆盖位置与非法输入

官方链表为 1→2→3→4→5。Test1 查询 k=2，返回中间节点4；Test2 查询 k=1，返回尾节点5；Test3 查询 k=5，返回头节点1。三组正例覆盖同步移动、零间隔和先行后无需同步。

Test4 在空链表上查询100；Test5 查询超过长度的6；Test6 查询0，三者都返回空。它们分别锁定空结构、先行不足和非法计数，不能合并成一个模糊的“边界测试”。

#include <cassert>
 
void testKthFromEnd() {
    ListNode n5{5, nullptr};
    ListNode n4{4, &n5};
    ListNode n3{3, &n4};
    ListNode n2{2, &n3};
    ListNode n1{1, &n2};
 
    assert(findKthToTail(&n1, 2) == &n4);
    assert(findKthToTail(&n1, 1) == &n5);
    assert(findKthToTail(&n1, 5) == &n1);
    assert(findKthToTail(nullptr, 100) == nullptr);
    assert(findKthToTail(&n1, 6) == nullptr);
    assert(findKthToTail(&n1, 0) == nullptr);
 
    ListNode only{9, nullptr};
    assert(findKthToTail(&only, 1) == &only);
    assert(findKthToTail(&only, 2) == nullptr);
}

单节点补充测试验证先行0步和长度不足。若使用动态分配构造链表，测试结束必须统一销毁头链，不能释放返回的借用节点后再销毁整链。

随机测试可先把节点地址按正序收集到向量，对每个合法 k 断言结果等于 vector[length-k]，并对0和大于长度断言空。这种参考模型只用于测试，不改变生产算法的单遍扫描约束。

可迁移的双指针模式

固定距离还能用于删除倒数第k个节点：常让 ahead 从哨兵节点先行 k+1 个位置，使 behind 停在目标前驱，再重连 next。这里多出的一个位置来自“需要前驱”而非“需要目标”，不能照抄本题步数。

寻找中点使用速度比而非固定间隔：fast 每轮两步、slow 每轮一步，fast 到尾时 slow 到中间。偶数长度要先约定返回前中点还是后中点，再选择循环条件。

判圈也使用不同速度。它们共同的抽象是用两个位置之间的关系，把无法反向或随机访问的问题转换成前向扫描；真正可复用的是建立并证明不变量，而不是记住某个 while 条件。

正确性证明

先行成功后，ahead 位于正数第k个节点，behind位于第1个节点，二者相差 k-1 条边。同步阶段每次两者各走一条边，固定间隔保持不变。

ahead 从第k个节点到第n个尾节点共走 n-k 步，behind也走 n-k 步，从第1个到第 n-k+1 个节点。该位置按定义正是倒数第k个。若先行失败，则 n 小于 k，不存在目标，返回空正确。

入口排除了空链表和k为0；循环只在已知非空节点上读取 next。由间隔不变量、终止位置和防御检查可知，函数对全部合法无环输入返回唯一目标，对不可满足输入安全返回空。

本章练习

本章回顾

1. 倒数序号从1开始，倒数第1个是尾节点。
2. 作者让ahead先走k-1条边，再与behind同步到尾。
3. 固定间隔使ahead到第n个节点时behind位于第n-k+1个节点。
4. 先行k步并让ahead走到空是等价版本，但两套终点不能混搭。
5. 空链表、k为0和链表不足k个节点必须分别防御。
6. 算法时间 O(n)、额外空间 O(1)，无需预先知道长度。
7. 输入必须是遍历期间不变的无环链表，返回值只是借用节点。
8. 测试应比较节点身份，并覆盖作者三正例和三非法输入。

名词解释